有一个由 $N$ 个顶点构成的树（无向无环连通图）。顶点编号为 $1$ 到 $N$，边编号为 $1$ 到 $N-1$。最初所有顶点均为黑色。

编写一个程序执行以下两种查询：

• 1 i：翻转顶点 $i$ 的颜色。（白色 $\to$ 黑色，黑色 $\to$ 白色）
• 2 u：统计与 $u$ 相连的顶点 $v$ 的个数。两个顶点相连，表示连接它们的路径上所有顶点的颜色相同。

输入格式

第一行包含 $N$（$2 \le N \le 100{,}000$）。

接下来 $N-1$ 行，每行包含两个整数 $u$ 和 $v$，表示第 $i$ 条边连接的两个顶点。

下一行包含查询的个数 $M$（$1 \le M \le 100{,}000$）。

接下来 $M$ 行，每行给出一个查询。

输出格式

对于每个类型 2 的查询，按顺序在一行中输出结果。

样例

输入 1

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

输出 1

5
1

输入 2

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

输出 2

7
3
3