AT_abc014_4 [ABC014D] 閉路

[problemUrl]: https://atcoder.jp/contests/abc014/tasks/abc014_4 $ n $ 個の頂点と $ n-1 $ 本の辺からなる連結な無向グラフが与えられます．それぞれの頂点には $ 1 $ から $ n $ までの番号が順番にふられています． グラフ理論において，このような条件を満たすグラフは木と呼ばれ，閉路を含まないという性質があります． このグラフに対し，元のグラフに含まれない追加辺 $ (a,b) $ を1つ追加したグラフについて考えてみると，このグラフはちょうど1つの閉路を含みます． あなたの仕事は，そのようなグラフについて，閉路の長さ(閉路に含まれる辺の数)を出力することです．ただ，追加辺の候補はいくつかあり，$ Q $ 個与えられるので，それら全ての候補について答えを出力してください．

入力は以下の形式で標準入力から与えられる． > $ N $ $ x_1\ y_1 $ $ x_2\ y_2 $ ： $ x_{N-1}\ y_{N-1} $ $ Q $ $ a_1\ b_1 $ $ a_2\ b_2 $ ： $ a_{Q}\ b_{Q} $ - $ 1 $ 行目には，グラフの頂点数を表す整数 $ N\ (1≦N≦100,000) $ が与えられる． - 続く$ 2 $ 行目から$ N-1 $行は，グラフの辺情報を表す．$ i $番目の行には，辺が結ぶ頂点 $ x_i $ と $ y_i $が空白区切りで与えられる． - 続く$ 1+N $ 行目には，辺$ (a,b) $の候補の数を表す整数 $ Q\ (1≦Q≦100,000) $ が与えられる． - 続く$ 2+N $ 行目から$ Q $行は，$ i $番目の追加辺候補の情報を表す．$ i $ 番目の行には，追加辺が結ぶ頂点 $ a_i $ と $ b_i $が空白区切りで与えられる． - 与えられる辺は全て，存在する頂点を結んでいる． - グラフは自己辺を含まない．つまり，任意の$ i $について，$ x_i≠y_i $が成り立つ． - グラフは多重辺を含まない．つまり，任意の$ i,j(i≠j) $について，$ x_i≠x_j $もしくは$ y_i≠y_j $が成り立つ． - 追加辺は，元のグラフに含まれない辺であり自己辺でないことが保障されている．

全ての追加辺候補について，それを元のグラフに追加したときにできる閉路の長さを，$ 1 $ 行目から $ Q $ 行順番に出力せよ．出力の末尾に改行を入れること．

### 部分点 この問題には2つのデータセットがあり，データセット毎に部分点が設定されている． - $ Q=1 $ を満たすデータセット 1 に正解した場合は $ 30 $ 点が与えられる． - 追加制約のないデータセット 2 に正解した場合は，上記のデータセットとは別に $ 70 $ 点が与えられる． ### Sample Explanation 1 図は以下の通りです．