题面描述

一棵以1为根的树，一共 $n$ 个节点，每一个节点都有颜色，初始时颜色编号都为 1 。

一共进行 $m$ 次操作，操作有两种：

• 1 x y ：把以 $x$ 为根的子树的全部节点染成 $y$ 号颜色。
• 2 x ：询问把连接不同颜色的点的边删掉后，$x$ 所在的连通块大小。边不实际删掉。

输入格式

第一行一个整数 $n$ 。

接下来 $n-1$ 行描述这棵树，每行两个整数 $u,v$ ，表示树上的一条边。

第 $n+1$ 行一个整数 $m$ 。

接下来 $m$ 行，每行一个操作，格式如题面所述。

输出格式

对于每一个操作2，输出一行一个整数表示答案。

样例一

input

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

output

5
4
3

explanation

我们用红色表示1，绿色表示2，这是初始的各点颜色，此时询问节点2的答案是5：

这是第一次修改后的树，此时询问节点1的答案是4：

这是第二次修改后的树，此时询问节点5的答案是3：

样例二

input

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

3
6
3
4
4

限制与约定

对于所有数据，$1\leq n\leq 10^6$ ，$1\leq m \leq 10^6$ ，$1\leq y\leq n$ 。

时间限制：2s

空间限制：1024MB