题目描述

有一片由 $n$ 个能量塔组成的树形网络，1号塔为网络中枢（即根节点）。每个能量塔都配备了一盏信号灯，初始时所有信号灯均处于熄灭状态。网络运行期间会发生 $m$ 次状态变动，具体分为以下几类：

1 k：切换第 $k$ 号能量塔的信号灯状态（亮着的则熄灭，熄灭的则点亮）。

2 a b：查询网络中与 $a$ 号塔处于同一层级（深度相同）的能量塔中，那些与 $a$ 号塔的路径距离为 $b$ 且信号灯处于点亮状态的塔的数量。

3 t：将整个网络的信号灯状态回溯到第 $t$ 次变动完成后的状态。

请针对每类 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）：所有查询中 $b$ 为奇数（即 $b \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 t$。