- Prepare
- Algorithms
- Graph Theory
- Tree Splitting

# Tree Splitting

# Tree Splitting

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 .