Given a tree with vertices numbered from to . You need to process queries. Each query represents a vertex number encoded in the following way:
Queries are encoded in the following way: Let, be the query and be the answer for the query where and is always . Then vertex . We are assure that is between and , and hasn't been removed before.
Note: is the bitwise XOR operator.
For each query, first decode the vertex and then perform the following:
- Print the size of the connected component containing .
- Remove vertex and all edges connected to .
Input Format
The first line contains a single integer, , denoting the number of vertices in the tree.
Each line of the subsequent lines (where ) contains space-separated integers describing the respective nodes, and , connected by edge .
The next line contains a single integer, , denoting the number of queries.
Each line of the subsequent lines contains a single integer, vertex number .
Constraints
Output Format
For each query, print the size of the corresponding connected component on a new line.
Sample Input 0
3
1 2
1 3
3
1
1
2
Sample Output 0
3
1
1
Sample Input 1
4
1 2
1 3
1 4
4
3
6
2
6
Sample Output 1
4
3
2
1
Explanation
Sample Case 0:
We have, = 0 and connected component :
has vertex = = = . The size of connected component containing is .
So, = .
Removing vertex and all of it's edges, we get two disconnected components :
has vertex = = = . The size of connected component containing is .
So, = .
Removing vertex and all of it's edges, we are left with only one component :
has vertex = = = . The size of connected component containing is .
So, = .
Removed vertex .
Sample Case 1:
We have, = and connected component :
has vertex = = = . The size of connected component containing is .
So, = .
Removing vertex and all of it's edges, we get component :
has vertex = = = . The size of connected component containing is .
So, = .
Removing vertex and all of it's edges, now, we get two disconnected components :
has vertex = = = . The size of connected component containing is .
So, = .
Removing vertex and all of it's edges, now we are left with only one component :
has vertex = = = . The size of connected component containing is .
So, = .
Removed vertex .