题目描述

这里有一棵 $n$ 个结点根为 $1$ 号结点的树，每个结点上都有一盏灯，初始状态都是关闭。现在有 $m$ 次事件发生，有以下几种情况：

1 x 将 $x$ 位置上的灯打开或关闭（原来如果打开就关闭，否则打开）。

2 x y 询问树上与 $x$ 相同深度的点中与 $x$ 结点距离为 $y$ 的点中开着的灯的个数。

3 x 回到第 $x$ 次事件发生之后的状态。

对于每个 $2$ 询问请给出回答。

输入格式

第一行一个数 $n$ 。 接下来 $n-1$ 行每行两个数 $u,v$ 表示 $u$ 与 $v$ 之间一条边。接下来一个数 $m$，下面的 $m$ 行每行二或三个数表示事件的发生。

输出格式

对于每次 $2$ 询问，给出答案。

3
1 2
1 3
6
1 3
2 2 2
1 2
2 2 2
1 3
2 2 2

1
1
0

提示

本题采用打包测评。

• Subtask 1（10 pts）：满足所有询问中 $y \bmod 2=1$。

• Subtask 2（20 pts）：$n,m\leq 10$。

• Subtask 3（30 pts）：$n,m\leq 10^3$。

• Subtask 4（40 pts）：$n,m\leq 10^5$。

对于 $100\%$ 的数据，$1\leq n,m\leq 10^5$，$3$ 操作保证 $0 \leq x$。