AT_tenka1_2015_final_f 根付き木のみさわさん

[problemUrl]: https://atcoder.jp/contests/tenka1-2015-final/tasks/tenka1_2015_final_f 高橋君の家の庭には、頂点 $ 1 $ を根とする一本の根付き木である、みさわさんが生えています。 $ i $ 日目の朝、みさわさんは $ M_i $ 個の頂点 $ v_{i,1},\ …,\ v_{i,M_i} $ に実をつけます。 しかし、同じ日の晩には鳥がやってきて、残っているすべての実を食べてしまいます。 高橋君は、一日に一回、みさわさんの頂点をひとつ選んでゆさぶることができます。 頂点 $ w $ をゆさぶると、$ w $ の子孫 ($ w $ 自身も含む) である頂点についている実をすべて得られます。 高橋君は、 $ i $ 日目に、みさわさんから $ K_i $ 個以上の実を取りたいです。 高いところが好きな高橋君のために、ゆさぶることで $ K_i $ 個以上の実を得ることができる頂点のうち、根からもっとも遠いものをもとめ、その根からの距離を教えてください。 ただし、各頂点に対し、根からの距離とは、根からその頂点への唯一の単純なパスに含まれる辺の数を表します。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ a_1 $ $ b_1 $ $ a_2 $ $ b_2 $ : $ a_{N-1} $ $ b_{N-1} $ $ Q $ $ M_1 $ $ K_1 $ $ v_1_1 $ $ v_1_2 $ ... $ v_1_{M_1} $ : $ M_Q $ $ K_Q $ $ v_Q_1 $ $ v_Q_2 $ ... $ v_Q_{M_Q} $ - $ 1 $ 行目には、みさわさんの頂点の個数を表す整数 $ N $ ($ 3≦N≦10^5 $) が与えられる。 - $ 2 $ 行目からの $ N-1 $ 行のうち $ i $ 行目には、$ i $ 番目の辺の接続している $ 2 $ 頂点を表す整数 $ a_i,b_i $ ($ 1≦a_i＜b_i≦N $) が空白区切りで与えられる。 - このとき、みさわさんが木であることが保証されている。 - $ N+1 $ 行目には、高橋君が実を取りつづける日数を表す整数 $ Q\ (1≦Q≦10^5) $ が与えられる。 - $ N+2 $ 行目からの $ 2Q $ 行のうち、 - $ 2i-1 $ 行目には、$ i $ 日目にみさわさんがつける実の数を表す整数 $ M_i $ と、高橋君が取りたい実の数を表す整数 $ K_i $ ($ 1\ ≦\ K_i\ ≦\ M_i\ ≦\ N $) が与えられ、 - $ 2i $ 行目には、$ i $ 日目にみさわさんが実をつける頂点を表す $ M_i $ 個の整数が与えられる。 - 但し、入力は $ ΣM_i\ ≦\ 10^5 $ をみたす。

$ Q $ 日分の入力について、条件を満たす頂点のうち、根からもっとも遠い頂点までの距離を、 $ 1 $ 行ずつ出力せよ。 出力の末尾には改行を入れること。

### 部分点 この問題には部分点が設定されている。 - $ 1≦N≦100 $ を満たすデータセットに正解した場合は $ 20 $ 点が得られる。 - 全てのデータセットに正解した場合はさらに $ 110 $ 点が得られる。合計で $ 130 $ 点となる。 ### Sample Explanation 1 \- $ 1 $ つ目のクエリでは、みさわさんは $ 2 $ つの頂点 $ 4,5 $ に実をつけます。このうち $ 2 $ つの実を得られる頂点のうち、もっとも根から遠い頂点は $ 3 $ であり、この頂点の根からの距離は $ 2 $ です。 - $ 2 $ つ目のクエリでは、みさわさんは $ 1 $ つの頂点 $ 1 $ に実をつけます。このうち $ 1 $ つの実を得られる頂点のうち、もっとも根から遠い頂点は $ 1 $ であり、この頂点の根からの距離は $ 0 $ です。 - $ 3 $ つ目のクエリでは、みさわさんは $ 2 $ つの頂点 $ 2,1 $ に実をつけます。このうち $ 1 $ つの実を得られる頂点のうち、もっとも根から遠い頂点は $ 2 $ であり、この頂点の根からの距離は $ 1 $ です。