問題文

1 から N のついた N 個の頂点からなる、頂点 1 を根とする木が与えられます。辺は N-1 個あり、i 番目の辺は頂点 a_i と頂点 b_i を結んでいます。

クエリが Q 回与えられるので、処理してください。i 番目のクエリでは u_i, v_i が与えられるので、u_i と v_i の「最小共通祖先」、すなわち u_i の祖先でも v_i の祖先でもあるものであって、深さが最も深い頂点 p の番号を出力します。

ここで、頂点 x の「祖先」とは、x から根まで親方向にたどったときに通る頂点の集合であり、頂点 x や根も x の祖先に含みます。また、頂点 x の「深さ」とは、x から根まで到達するときに通る辺の個数の最小値とします。根の深さは 0 です。

入力例

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

出力例

1
3
1

• 頂点 1 は、頂点 4 の祖先でも頂点 6 の祖先でもある唯一の頂点です。よって、頂点 4, 6 の最小共通祖先は頂点 1 です。
• 頂点 5 の祖先でも頂点 6 の祖先でもある頂点は頂点 1, 3 の 2 つがありますが、その中で深さが最も深いものは頂点 3 です。よって、頂点 5, 6 の最小共通祖先は頂点 3 です。
• 頂点 1 は、頂点 1 の祖先でも頂点 5 の祖先でもある唯一の頂点です。よって、頂点 1, 5 の最小共通祖先は頂点 1 です。「頂点 x は頂点 x の祖先である」ことに注意してください。