Description

There is a tree with $n$ nodes, rooted at node $1$. Each node has a lamp, and all lamps are initially off. Now $m$ events occur, in the following forms:

1 x Toggle the lamp at node $x$ (turn it off if it is on, otherwise turn it on).

2 x y Query the number of nodes whose lamps are on among the nodes that are at the same depth as node $x$ and have distance $y$ from node $x$ in the tree.

3 x Revert to the state right after the $x$-th event.

For each query of type $2$, output the answer.

Input Format

The first line contains an integer $n$.
The next $n-1$ lines each contain two integers $u, v$, indicating an edge between $u$ and $v$.
Then an integer $m$ follows. The next $m$ lines each contain two or three integers describing an event.

Output Format

For each query of type $2$, output the answer.

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

1
1
0

Hint

This problem uses bundled evaluation.

• Subtask 1 (10 pts): For all queries, $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$.

For $100\%$ of the testdata, $1 \leq n, m \leq 10^5$, and operations of type $3$ guarantee $0 \leq x$.

Translated by ChatGPT 5