1828 - Lowest Common Ancestor

問題

$N$個の頂点を持つ木状のグラフが与えられます。
$Q$個の質問が与えられるので回答を出力してください。
・頂点$x$,頂点$y$の最小共通祖先
最小共通祖先とは頂点1-頂点$x$間の最短経路上にあり、頂点1-頂点$y$間の最短経路上にある、頂点1から最も遠い頂点のことを指す。

入力

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

$N$
$A_1$ $B_1$
$A_2$ $B_2$
 :
$A_{N-1}$ $B_{N-1}$
$Q$
$x_1$ $y_1$
$x_2$ $y_2$
 :
$x_Q$ $y_Q$

$A_i,B_i$は辺$i$によって頂点$A_i$と頂点$B_i$がつながっていることを示している。

出力

各質問の答えを改行区切りで出力してください。
出力の最後に改行を入れること。

制約

全ての入出力ケースについて以下を満たす。

• $2 \leq N \leq 10^{4}$
• $1 \leq Q \leq 10^{4}$
• $1 \leq A_i,B_i \leq N$
• $A_i \ne B_i(1 \leq i \leq N)$
• $1 \leq x_i,y_i \leq N$
• $x_i \ne y_i(1 \leq i \leq N)$
• 入力はすべて整数

入出力例

入力例1

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

出力例1

2
1

入力例2

2
1 2
1
1 2

出力例2

1