入力

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

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が成り立つ．
• 追加辺は，元のグラフに含まれない辺であり自己辺でないことが保障されている．

部分点

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

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

出力

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