AtCoder Beginner Contest 014

D - 閉路


Time limit時間制限 : 2sec / Memory limitメモリ制限 : 256MB

問題文

n 個の頂点と n-1 本の辺からなる連結な無向グラフが与えられます.それぞれの頂点には 1 から n までの番号が順番にふられています.

グラフ理論において,このような条件を満たすグラフは木と呼ばれ,閉路を含まないという性質があります. このグラフに対し,元のグラフに含まれない追加辺 (a,b) を1つ追加したグラフについて考えてみると,このグラフはちょうど1つの閉路を含みます. あなたの仕事は,そのようなグラフについて,閉路の長さ(閉路に含まれる辺の数)を出力することです.ただ,追加辺の候補はいくつかあり,Q 個与えられるので,それら全ての候補について答えを出力してください.


入力

入力は以下の形式で標準入力から与えられる.

N
x_1\ y_1
x_2\ y_2x_{N-1}\ y_{N-1}
Q
a_1\ b_1
a_2\ b_2a_{Q}\ b_{Q}
  • 1 行目には,グラフの頂点数を表す整数 N (1≦N≦100,000) が与えられる.
  • 続く2 行目からN-1行は,グラフの辺情報を表す.i番目の行には,辺が結ぶ頂点 x_iy_iが空白区切りで与えられる.
  • 続く1+N 行目には,辺(a,b)の候補の数を表す整数 Q (1≦Q≦100,000) が与えられる.
  • 続く2+N 行目からQ行は,i番目の追加辺候補の情報を表す.i 番目の行には,追加辺が結ぶ頂点 a_ib_iが空白区切りで与えられる.
  • 与えられる辺は全て,存在する頂点を結んでいる.
  • グラフは自己辺を含まない.つまり,任意のiについて,x_i≠y_iが成り立つ.
  • グラフは多重辺を含まない.つまり,任意のi,j(i≠j)について,x_i≠x_jもしくはy_i≠y_jが成り立つ.
  • 追加辺は,元のグラフに含まれない辺であり自己辺でないことが保障されている.

部分点

この問題には2つのデータセットがあり,データセット毎に部分点が設定されている.

  • Q=1 を満たすデータセット 1 に正解した場合は 30 点が与えられる.
  • 追加制約のないデータセット 2 に正解した場合は,上記のデータセットとは別に 70 点が与えられる.

出力

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


入力例1

5
1 2
1 3
1 4
4 5
3
2 3
2 5
2 4

出力例1

3
4
3

図は以下の通りです.


入力例2

6
1 2
2 3
3 4
4 5
5 6
4
1 3
1 4
1 5
1 6

出力例2

3
4
5
6

入力例3

7
3 1
2 1
2 4
2 5
3 6
3 7
5
4 5
1 6
5 6
4 7
5 3

出力例3

3
3
5
5
4

Submit提出する