#P18483. Jumping Lights

Jumping Lights

Jumping Lights

给你一棵树,即一张有 nn 个顶点、n−1n-1 条边的无向连通图。最开始,没有任何顶点被标记。你需要处理 qq 次下列三种操作:

  • 0 w:取消顶点 ww 的标记。如果它原本没有被标记,则什么也不做。
  • 1 w:标记顶点 ww。如果它原本已经被标记,则什么也不做。
  • 2:同时对树中的所有顶点进行以下更新:如果该顶点有至少一个已被标记的邻点,则将该顶点标记;否则取消该顶点的标记。

第三种操作的所有判断都使用操作前的标记状态。顶点不把自己当作邻点;它原先被标记,并不能单独保证更新后仍被标记。

每次操作后,求树中已被标记的顶点数量。

输入格式

第一行包含两个整数 n,qn,q(2≤n≤3⋅1052\le n\le3\cdot10^5,1≤q≤1061\le q\le10^6),分别表示顶点数和操作数。

接下来 n−1n-1 行,每行两个整数 u,vu,v(1≤u,v≤n1\le u,v\le n),表示树的一条边。

接下来 qq 行,每行按照上面的格式描述一次操作。对于前两种操作,1≤w≤n1\le w\le n。

输出格式

输出一行,包含 qq 个整数,第 ii 个整数表示第 ii 次操作后已被标记的顶点数量。

原样例 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