你的儿子 JOI-kun 很喜欢宠物。你的花园里有 $N$ 个小屋，编号为 $1$ 到 $N$。有 $N-1$ 条双向路径连接这些小屋，且已知任意两个小屋之间都可以通过路径相互到达。每个小屋最多只能容纳一只宠物。

JOI-kun 想要养猫和狗，但他担心它们经常会打架。因此，对于每个小屋处于以下三种状态之一（有猫、有狗、无宠物）的情况，他定义了花园的“危险等级”如下：

• 为了使每只猫和每只狗都无法通过未被阻断的路径相遇，所需要阻断的路径的最小数量。

在定义了危险等级后，JOI-kun 开始制定一个为期 $Q$ 天的花园使用计划。最初，没有任何小屋有宠物。第 $i$ 天的计划是以下三种情况之一：

• 在当前没有宠物的小屋 $v$ 中放入一只新猫。
• 在当前没有宠物的小屋 $v$ 中放入一只新狗。
• 将小屋 $v$ 中的宠物送走（即小屋 $v$ 将不再有宠物）。

作为家长，你需要负责检查你儿子的计划是否危险。具体来说，你需要求出在 $Q$ 天中每一天的计划执行后，花园的危险等级。

样例

输入格式 1

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

输出格式 1

1
2
1

说明

考虑有 $5$ 个小屋和 $4$ 条路径的情况，路径连接：小屋 $1$ 和小屋 $2$，小屋 $2$ 和小屋 $3$，小屋 $2$ 和小屋 $4$，以及小屋 $4$ 和小屋 $5$。

1. 假设他首先在小屋 $3$ 放入一只猫，在小屋 $5$ 放入一只狗。通过阻断小屋 $2$ 和小屋 $4$ 之间的路径，可以防止猫和狗相遇。因此，此时的危险等级为 $1$。
2. 假设他随后在小屋 $2$ 放入一只新猫，在小屋 $1$ 放入一只新狗。通过阻断小屋 $2$ 和小屋 $4$ 之间的路径以及小屋 $1$ 和小屋 $2$ 之间的路径，可以防止猫和狗相遇。因此，此时的危险等级为 $2$。
3. 假设他最后将小屋 $2$ 中的猫送走。他只需要阻断小屋 $2$ 和小屋 $3$ 之间的路径，所以现在的危险等级为 $1$。

子任务

共有 $3$ 个子任务。各子任务的分数和数据范围如下：

实现细节

你需要实现 $4$ 个函数：initialize、cat、dog 和 neighbor。 在开始时，系统会调用 initialize 函数来接收花园的信息。

• initialize(N, A, B)
  • $N$：花园中小屋的数量。
  • $A, B$：长度为 $N-1$ 的数组。它们表示对于 $0 \le i \le N-2$，小屋 $A_i$ 和小屋 $B_i$ 之间存在一条路径。保证任意两个不同的小屋之间都可以通过路径相互到达。

然后，对于 $Q$ 天中的每一天，按时间顺序调用对应当天计划的函数：

• cat(v)：当在小屋 $v$ 中放入一只新猫时调用，此时小屋 $v$ 没有宠物。
• dog(v)：当在小屋 $v$ 中放入一只新狗时调用，此时小屋 $v$ 没有宠物。
• neighbor(v)：当小屋 $v$ 中的宠物离开时调用。

这些函数应返回计划执行后的危险等级。 注意，这些函数调用所产生的状态改变会持续存在。

样例评测程序

样例评测程序按以下格式读取输入：

• 第 $1$ 行：$N$
• 第 $2+i$ 行 ($0 \le i \le N-2$)：$A_i \ B_i$
• 第 $N+1$ 行：$Q$
• 第 $N+2+j$ 行 ($0 \le j \le Q-1$)：$T_j \ v_j$

其中，若 $T_j = 1$，则第 $(j+1)$ 天的函数调用为 cat(v_j)；若 $T_j = 2$，则为 dog(v_j)；若 $T_j = 3$，则为 neighbor(v_j)。

样例评测程序按以下格式输出第 $(j+1)$ 天函数调用的返回值 $D_j$：

• 第 $1+j$ 行 ($0 \le j \le Q-1$)：$D_j$