题目描述

译自 JOI Open 2018 T2 「猫か犬 / Cats or Dogs」

你的儿子 JOI 君喜欢养宠物。在你家的花园里有 $N$ 个小屋可供饲养宠物，这 $N$ 个房子从 $1$ 到 $N$ 编号。有 $N-1$ 条双向路径双向连接这 $N$ 个小屋，并且对于任意两个小屋，都可以通过某些路径在它们之间移动。每个小屋最多可以住一只宠物。

JOI 君想要养猫和狗，但是他很担心宠物们可能会经常打架。对于每个小屋的如下状态：住了一只猫，住了一只狗，没有住宠物，他都按如下方式定义了花园的危险级别：

• 为了不让任何一只猫和任何一只狗通过未阻塞的道路相遇，需要阻塞的最小路径数。

在定义危险级别后，JOI 君开始指定后 $Q$ 天使用花园的计划。初始时，所有小屋里都没有宠物。第 $i$ 天的计划是如下内容中的一个：

• 在目前没有宠物的小屋 $v$ 中养一只猫。

• 在目前没有宠物的小屋 $v$ 中养一只狗。

• 将小屋 $v$ 中的宠物送给邻居，这意味着在小屋 $v$ 中就没有宠物了。

你作为家长，有责任检查你的儿子的计划是否危险。更确切地说，你需要求出这 $Q$ 天每天进行完计划后，这个花园的危险级别。

实现细节

你需要实现四个函数 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$ 中养一只猫。

dog(v)：调用此函数，在目前没有宠物的小屋 $v$ 中养一只狗。

neighbor(v)：调用此函数，让小屋 $v$ 中的宠物离开。

这些函数应返回在这个计划执行后花园的危险值。

C++ 的提交应引入库 catdog.h 来完成，目前不支持对 Java 和 Pascal 语言提交的测评。

输入格式

第一行一个整数 $N$。

接下来 $N-1$ 行，每行两个整数 $A_i, B_i$。

接下来一行一个整数 $Q$。

接下来 $Q$ 行，每行两个整数 $T_j, v_j$。

输出格式

第 $j$ 行输出 $D_j$。

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

0
0
2
0

数据规模与约定

$1 < N \leq 100000$

$1 < Q \leq 100000$