There is a tree rooted at 1 with $n$ nodes. Each node has a color, and initially, all nodes have color 1.

There are $m$ operations of two types:

• 1 x y: Change the color of all nodes in the subtree rooted at $x$ to color $y$.
• 2 x: Query the size of the connected component containing $x$ if all edges connecting nodes of different colors were removed. The edges are not actually removed.

Input

The first line contains an integer $n$.

The next $n-1$ lines describe the tree, each containing two integers $u, v$, representing an edge in the tree.

The $(n+1)$-th line contains an integer $m$.

The next $m$ lines each contain an operation, formatted as described above.

Output

For each type 2 operation, output one integer per line representing the answer.

Examples

Input 1

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

Output 1

5
4
3

Note 1

We use red to represent color 1 and green to represent color 2. This is the initial coloring of the nodes; the answer for node 2 is 5:

This is the tree after the first modification; the answer for node 1 is 4:

This is the tree after the second modification; the answer for node 5 is 3:

Input 2

10
1 2
2 3
1 4
2 5
3 6
2 7
6 8
8 9
9 10
15
1 4 10
1 2 4
1 1 5
1 7 10
1 8 10
2 8
2 2
1 1 5
1 3 4
1 9 9
1 4 6
2 6
2 1
1 4 4
2 2

Output 2

3
6
3
4
4

Constraints

For all data, $1\leq n\leq 10^6$, $1\leq m \leq 10^6$, $1\leq y\leq n$.