D. Sakurako and Chefir

Given a tree with vertices rooted at vertex . While walking through it with her cat Chefir, Sakurako got distracted, and Chefir ran away.

To help Sakurako, Kosuke recorded his guesses. In the -th guess, he assumes that Chefir got lost at vertex and had stamina.

Also, for each guess, Kosuke assumes that Chefir could move along the edges an arbitrary number of times:

• from vertex to vertex , if is an ancestor of , the stamina will not change;
• from vertex to vertex , if is not an ancestor of , then Chefir's stamina decreases by .

If Chefir's stamina is , he cannot make a move of the second type.

For each assumption, your task is to find the distance to the farthest vertex that Chefir could reach from vertex , having stamina.

Vertex is an ancestor of vertex if the shortest path from to the root passes through .

The first line contains a single integer ( ) — the number of test cases.

Each test case is described as follows:

• The first line contains a single integer ( ) — the number of vertices in the tree.
• The next lines contain the edges of the tree. It is guaranteed that the given edges form a tree.
• The next line consists of a single integer , which denotes the number of guesses made by Kosuke.
• The next lines describe the guesses made by Kosuke, with two integers , .

It is guaranteed that the sum of and the sum of across all test cases does not exceed .

For each test case and for each guess, output the maximum distance to the farthest vertex that Chefir could reach from the starting point having stamina.

输入 #1

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

输出 #1

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

In the first example:

• In the first query, you can go from vertex to vertex (after which your stamina will decrease by and become ), and then you can go to vertex ;
• In the second query, from vertex with stamina, you can only reach vertices , , , and ;
• In the third query, from vertex with stamina, you can only reach vertices , , , and ;