問題文

N 頂点の木があり、頂点には 1, 2, \cdots, N と番号づけられています。i 番目 (1 \leq i \leq N-1) の辺は、頂点 A_i と B_i を結んでいます。

以下の形式の質問が Q 個与えられるので、j = 1, 2, \cdots, Q の順に答えてください。

• N-1 本の辺のうち何本かを、残す辺として選ぶ。
• 選ばれなかった辺を削除したとき、頂点 V_{j,1},V_{j,2}, \cdots ,V_{j,K_j} すべてが互いに連結となるようにしたい。
• 最小で何本の辺を選ぶ必要があるか？

制約

• 2 \leq N \leq 100000
• 1 \leq A_i \lt B_i \leq N
• 1 \leq Q \leq 100000
• 2 \leq K_j \leq N
• 1 \leq V_{j,1} \lt V_{j,2} \lt \cdots \lt V_{j,K_j} \leq N
• K_1 + K_2 + \cdots + K_Q \leq 200000
• 与えられるグラフは木である
• 入力はすべて整数

小課題・得点

この問題はいくつかの小課題に分けられ、その小課題のすべてのテストケースに正解した場合に「この小課題に正解した」とみなされます。
提出したソースコードの得点は、正解した小課題の点数の合計となります。

1. (2 点)：N,Q \leq 5000
2. (1 点)：K_j = 2
3. (1 点)：K_j = 3
4. (3 点)：追加の制約はない。

入力例 1

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

出力例 1

1
3
4
4
5

1 番目の質問においては、頂点 1 と頂点 2 は 1 番目の辺によって隣接しているため、この辺のみを選べばよいです。
残りの質問についても同様に答えが導けます。

なお、この入力は小課題 1, 4 の制約を満たします。

入力例 2

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

出力例 2

1
1
2
1
2

この入力は小課題 1, 2, 4 の制約を満たします。

入力例 3

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

出力例 3

2
2
3
4
5

この入力は小課題 1, 3, 4 の制約を満たします。