题目描述

一片森林中有 $n$ 盏信号灯，它们由 $n-1$ 条道路连接成一棵树。起初所有信号灯都处于未标记状态。

维护员会依次进行 $q$ 次操作。除了手动打开或关闭某一盏灯外，还有一种特殊的“跳跃同步”操作：所有信号灯同时观察自己相邻的灯，如果至少有一个相邻灯在操作前是标记状态，那么它在操作后变为标记状态；否则它在操作后变为未标记状态。

你需要在每次操作后，报告当前有多少个顶点处于标记状态。

操作共有三种：

• 0 w：取消标记顶点 $w$；如果 $w$ 本来未被标记，则什么也不发生。
• 1 w：标记顶点 $w$；如果 $w$ 本来已经被标记，则什么也不发生。
• 2：对整棵树同时执行一次跳跃同步：每个顶点如果至少有一个被标记的邻居，则变为标记；否则变为未标记。

注意第三种操作是同时发生的，判断邻居是否被标记时应使用操作前的状态。

输入格式

第一行包含两个整数 $n,q$，分别表示树的顶点数和操作数。

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

接下来 $q$ 行，每行表示一次操作，格式如题目描述所示。对于带参数的操作，满足 $1\le w\le n$。

输出格式

输出一行 $q$ 个整数，第 $i$ 个整数表示第 $i$ 次操作结束后，树中被标记的顶点数量。

数据范围

• $2\le n\le 3\cdot 10^5$；
• $1\le q\le 10^6$；
• $1\le u,v\le n$。

样例 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 2 6 5 4 3 3 1

样例 2

输入

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

输出

1 2 1 2 2