Problem Description

In Takahashi's garden, there is a single rooted tree with vertex $1$ as the root, known as Miss Misawa.

On the morning of the $i$-th day, Miss Misawa will bear fruit on $M_i$ vertices $v_{i,1}, \ldots, v_{i,M_i}$.

However, birds will come and eat all the remaining fruits on the same evening.

Takahashi can shake one vertex of Miss Misawa once a day.

Shaking vertex $w$ will allow Takahashi to obtain all the fruits on the vertices that are descendants of $w$ (including $w$ itself).

Takahashi wants to obtain at least $K_i$ fruits from Miss Misawa on the $i$-th day.

For Takahashi, who likes high places, please find the vertex that allows him to obtain at least $K_i$ fruits and is the farthest from the root, and then tell him the distance from the root to that vertex.

For each vertex, the distance from the root is defined as the number of edges in the unique simple path from the root to that vertex.

Input Format

The input is given from the standard input in the following format:

$ 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} $

• The first line contains an integer $ N $ ($3 \leq N \leq 10^5$), representing the number of vertices in Miss Misawa.
• The next $ N-1 $ lines, where the $ i $-th line contains two integers $ a_i, b_i $ ($1 \leq a_i < b_i \leq N$), representing the two vertices connected by the $ i $-th edge.
• It is guaranteed that Miss Misawa is a tree.
• The $ N+1 $-th line contains an integer $ Q $ ($1 \leq Q \leq 10^5$), representing the number of days Takahashi will continue to collect fruits.
• The next $ 2Q $ lines, where
• the $ 2i-1 $-th line contains two integers $ M_i $ and $ K_i $ ($1 \leq K_i \leq M_i \leq N$), representing the number of fruits Miss Misawa will bear and the number of fruits Takahashi wants to collect on the $ i $-th day, respectively,
• the $ 2i $-th line contains $ M_i $ integers, representing the vertices where Miss Misawa will bear fruits on the $ i $-th day.
• The input satisfies $\Sigma M_i \leq 10^5$.

Output Format

For each of the $ Q $ days, output the distance from the root to the farthest vertex that satisfies the condition, one per line. End each output with a newline.

Sample Input and Output

Sample Input #1

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

Sample Output #1

2
0
1

Sample Input #2

10
4 10
2 3
1 4
1 2
3 5
1 8
4 6
8 9
2 7
5
10 4
9 7 3 1 5 10 4 6 2 8
2 2
8 2
10 9
6 2 10 4 7 1 5 8 9 3
2 2
10 2
5 1
1 7 2 3 9

Sample Output #2

1
0
0
0
2

Sample Input #3

15
3 4
4 6
11 13
2 6
4 8
7 13
4 7
8 9
1 8
5 9
8 15
9 14
8 12
9 10
5
14 5
5 1 13 8 14 3 2 9 7 10 11 4 12 15
5 5
6 8 12 2 11
1 1
12
12 8
2 13 1 10 12 3 8 9 6 4 7 15
10 8
8 14 13 12 15 10 7 5 2 4

Sample Output #3

2
1
2
1
1

Notes/Hints

Partial Points

This problem has partial points.

• If you solve the dataset where $1 \leq N \leq 100$, you will get $ 20 $ points.
• If you solve all datasets, you will get an additional $ 110 $ points, totaling $ 130 $ points.

Sample Explanation 1

• For the first query, Miss Misawa bears fruits on two vertices $ 4, 5 $. Among the vertices where Takahashi can obtain two fruits, the farthest from the root is vertex $ 3 $, with a distance of $ 2 $ from the root.
• For the second query, Miss Misawa bears a fruit on vertex $ 1 $. The farthest vertex from the root where Takahashi can obtain one fruit is vertex $ 1 $, with a distance of $ 0 $ from the root.
• For the third query, Miss Misawa bears fruits on two vertices $ 2, 1 $. Among the vertices where Takahashi can obtain one fruit, the farthest from the root is vertex $ 2 $, with a distance of $ 1 $ from the root.

见题面 Input 部分

见题面 Output 部分