题目

众所周知，在中国里程碑式的结论是：当 $n=10^6$ 时，$O(n^2)$ 的算法也能轻松通过一道题。（玩笑话）

给定一棵有 $n$ 个顶点、$n-1$ 条边的树，边依次记为 $(u_1,v_1),(u_2,v_2),\ldots,(u_{n-1},v_{n-1})$。
对每个顶点 $u$，我们都有一个集合 $S_u$，且初始时 $S_u=\{\,u\,\}$。

有两种操作：

• 1 u：输出有多少个集合 $S_v\ (1\le v\le n)$ 包含元素 $u$。

• 2 p：取第 $p$ 条边 $(u_p,v_p)$，将 $S_{u_p}$ 与 $S_{v_p}$ 做并集，并把并集赋值给二者：

  $$S_{u_p}\leftarrow S_{u_p}\cup S_{v_p},\qquad S_{v_p}\leftarrow S_{u_p}\cup S_{v_p}.$$

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

输入

• 第一行两个整数 $n,m\ (2\le n\le 2\times 10^5,\ 1\le m\le 6\times 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$）：
  • 若 $t=1$，代表操作 1 w（此时 $w$ 为顶点编号，$1\le w\le n$）；
  • 若 $t=2$，代表操作 2 w（此时 $w$ 为边的编号，$1\le w\le n-1$，对应边 $(u_w,v_w)$）。

输出

对每个第一类操作 1 u，输出一个整数作为答案，每个答案一行。

样例

输入

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

输出

5
2
3
4
5