Nicole and Birjik are seniors taking a break from job applications by creating the following game:
- Birjik draws a rooted tree with vertices numbered from to , rooted at vertex .
- Nicole creates queries. For each query, she takes a copy of the tree and colors of its vertices black, leaving the remaining vertices white.
- The goal of the game is to answer each query by finding the respective values of , where each is the number of subtrees containing exactly black vertices (including the subtree's root vertex).
For example, the diagram below depicts a query on a tree where and the black vertices are , , and :
Given the tree and queries, solve each query by printing the values of on a new line.
Input Format
The first line contains an integer, , denoting the number of vertices of the tree.
Each of the subsequent lines contains two space-separated integers, and , describing an edge connecting vertices and .
The next line contains an integer, , denoting the number of queries. The subsequent lines describe each query over two lines:
- The first line contains an integer denoting .
- The second line contains space-separated integers describing the respective IDs of the vertices to color black.
Constraints
- It is guaranteed that the given graph is a tree.
- It is guaranteed that the vertex IDs given in each query are distinct IDs that exist in the tree.
- The sum of over all queries in a test case is
Output Format
For each query, print a single line containing integers describing the respective values of . Recall that each is the total number of subtrees containing exactly black vertices.
Sample Input 0
7
1 2
1 3
1 4
2 5
3 7
3 6
2
3
5 7 2
3
7 6 5
Sample Output 0
2 3 1 1
1 4 1 1
Explanation 0
In this example, the graph and queries look like this:
We perform the following queries:
Color vertices , , and black:
We then print the respective values of as
2 3 1 1on a new line.Color vertices , , and black:
We then print the respective values of as
1 4 1 1on a new line.
Sample Input 1
7
2 1
1 3
4 1
7 4
3 5
3 6
3
3
5 2 1
4
7 6 2 4
2
3 1
Sample Output 1
3 3 0 1
1 4 1 0 1
5 1 1
Explanation 1
In this example, the graph and queries look like this:
Follow the same process as Sample Case 0 to verify the Expected Output values.