众所周知，在中国，对于 $n = 10^6$ 的问题，$O(n^2)$ 的算法可以轻松通过。

给定一棵包含 $n$ 个顶点和 $n - 1$ 条边 $(u_1, v_1), (u_2, v_2), \dots, (u_{n-1}, v_{n-1})$ 的树。对于每个顶点 $u$，都有一个集合 $S_u$。初始时 $S_u = \{u\}$。

有两种类型的操作：

• “1 $u$”：输出包含 $u$ 的集合 $S_v$ ($1 \le v \le n$) 的数量。
• “2 $p$”：取集合 $S_{u_p}$ 和 $S_{v_p}$，并将 $S_{u_p} \cup S_{v_p}$ 赋值给它们两者。

你需要执行 $m$ 次操作。对于每种第一类操作，输出答案。

输入格式

第一行包含两个整数 $n, m$ ($2 \le n \le 2 \cdot 10^5, 1 \le m \le 6 \cdot 10^5$)。

接下来的 $n - 1$ 行，每行包含两个整数 $u_i, v_i$，描述树的一条边 ($1 \le u_i, v_i \le n$)。

接下来的 $m$ 行，每行包含两个整数 $t, w$，描述一个操作 ($1 \le t \le 2, 1 \le w \le n + 1 - t$)。

输出格式

对于每种第一类操作，在单独的一行中输出一个整数。

样例

输入 1

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

输出 1

5
2
3
4
5