给定一棵树：一个包含 $n$ 个顶点和 $n-1$ 条边的无向连通图。初始时，所有顶点均未被标记。你的任务是处理 $q$ 个以下三种类型的查询：

• “0 $w$”：取消标记顶点 $w$；如果 $w$ 本身未被标记，则不进行任何操作。
• “1 $w$”：标记顶点 $w$；如果 $w$ 本身已被标记，则不进行任何操作。
• “2”：同时对树中所有顶点进行操作：如果一个顶点至少有一个被标记的邻居，则标记该顶点，否则取消标记该顶点。

在每次查询后，求出树中被标记的顶点数量。

输入格式

第一行包含两个整数 $n$ 和 $q$ ($2 \le n \le 3 \cdot 10^5$; $1 \le q \le 10^6$)，分别表示树的顶点数和查询次数。

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

接下来的 $q$ 行，每行表示一个上述格式的查询 ($1 \le w \le n$)。

输出格式

输出一行，包含 $q$ 个整数，表示每次查询后树中被标记的顶点数量。

样例

样例输入 1

8 8
1 2
2 3
2 4
1 5
5 6
5 7
5 8
1 1
2
2
0 1
0 3
0 4
0 5
2

样例输出 1

1 2 6 5 4 3 3 1

样例输入 2

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

样例输出 2

1 2 1 2 2