There is a tree (connected acyclic undirected graph) with $N$ vertices. The vertices are numbered $1$ to $N$, and the edges are numbered $1$ to $N-1$. Initially, all vertices are colored black.

Write a program that performs the following two types of queries:

• 1 i: Toggle the color of vertex $i$ (white $\to$ black, black $\to$ white).
• 2 u: Count the number of vertices $v$ that are connected to $u$. Two vertices are considered connected if all vertices on the path connecting them have the same color.

Input

The first line contains $N$ ($2 \le N \le 100{,}000$).

The next $N-1$ lines each contain two integers $u$ and $v$ — the endpoints of the $i$-th edge.

The next line contains the number of queries $M$ ($1 \le M \le 100{,}000$).

The next $M$ lines each contain a query.

Output

For each type 2 query, output the result on its own line, in order.

Examples

Input 1

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

Output 1

5
1

Input 2

7
1 2
1 3
2 4
2 5
3 6
3 7
4
2 1
1 1
2 2
2 3

Output 2

7
3
3