Tree - Lowest Common Ancestor

時間制限 : 1 sec, メモリ制限 : 131072 KB
英語版はこちら

LCA: Lowest Common Ancestor

根付き木の2頂点 u, v の共通祖先で最も根から遠い祖先(LCA: Lowest Common Ancestor)を求めよ。

木の節点には 0 を根とする 0 から n-1 までの番号を割りあてる。

入力

n
k0 c1 c2 ... ck0
k1 c1 c2 ... ck1
:
kn-1 c1 c2 ... ckn-1
q
u1 v1
u2 v2
:
uq vq

入力の最初の行に、木の節点の個数 n が与えられる。 続く n 行目に、各節点の情報が与えられる。ki は節点 i の子の数、c1, ... cki は節点 i の1番目の子の節点番号、... ki 番目の子の節点番号を示す。

続く行に質問の数 q が与えられる。続く q 行に2つの節点の組 u, v が与えられる。

出力

質問ごとに、uv の LCA となる節点の番号を1行に出力する

制約

  • 1 ≤ n ≤ 100000
  • 1 ≤ q ≤ 100000

入力例 1

8
3 1 2 3
2 4 5
0
0
0
2 6 7
0
0
4
4 6
4 7
4 3
5 2

出力例 1

1
1
0
0