[AdditionalFile5423.zip](file://AdditionalFile5423.zip?type=additional_file)

#5423. 「OOI 2017 Day 1」布谷鸟

标签: 传统 | 时间限制: 2000 ms | 内存限制: 512 MiB |

题目描述

题目译自 Open Olympiad in Informatics 2017 Day1 T1 「Кукушки / Cuckoos」。

英国科学家决定研究鸟类学，并观察一种特殊的布谷鸟的生活。为此，他们种植了一棵树，并在树上建造了 $n$ 个巢穴，每个巢穴中都住着一只布谷鸟。观察树木的过程包括在某些时刻评估是否可以将某个特定的蛋放入某个布谷鸟的巢穴中。

每个蛋只能在两个特定的巢穴中孵化。每个蛋由一对无序的不同数字 $(x, y)$ 表示。蛋 $(x, y)$ 可以在巢穴 $x$ 或 $y$ 中孵化，而不能在其他巢穴中孵化。注意，蛋 $(x, y)$ 与蛋 $(y, x)$ 是相同的。

现在描述将蛋放入现有巢穴的过程：假设科学家想将蛋 $(x, y)$ 放入巢穴 $x$。如果巢穴 $x$ 中没有蛋，那么蛋 $(x, y)$ 直接留在该巢穴中，此步骤的过程结束。如果巢穴 $x$ 中已经有一个蛋 $(x, p)$，那么布谷鸟会将蛋 $(x, y)$ 放入该巢穴，同时尝试将蛋 $(x, p)$ 以类似方式放入巢穴 $p$，此过程继续进行。

你需要回答科学家提出的问题。总共有三种类型的问题：

1. （理论性）如果将蛋 $(x, y)$ 放入巢穴 $x$，过程是否会结束？由于这是一个纯理论问题，蛋 不会实际添加，巢穴状态不变。
2. （实践性）如果将蛋 $(x, y)$ 放入巢穴 $x$，过程是否会结束？如果过程结束，蛋将 实际添加，按照描述的过程进行操作。
3. （理论性）存在多少 有序 数字对 $(x, y)$，使得蛋 $(x, y)$ 可以放入巢穴 $x$，并考虑当前巢穴中已有的蛋？每个蛋的答案独立于其他添加的蛋计算。

输入格式

第一行输入三个整数 $n, m, q$ $(2 \leq n \leq 200000, 0 \leq m \leq n, 1 \leq q \leq 600000)$，其中 $n$ 表示树上巢穴的数量，$m$ 表示科学家已经放入的蛋的数量，$q$ 表示科学家提出的问题数量。

接下来的 $m$ 行，每行包含两个数字 $x_i$ 和 $y_i$，表示巢穴 $x_i$ 中有一个蛋 $(x_i, y_i)$。保证所有 $x_i$ 均不同，且对于所有 $i$，$x_i \neq y_i$。

接下来的 $q$ 行描述科学家的问题。问题的顺序即为需要回答的顺序。每行第一个数字 $t_j$ 表示问题的类型。

• 如果 $t_j = 1$ 或 $t_j = 2$，则接下来是两个不同的数字 $x_j$ 和 $y_j$，描述问题中涉及的蛋。
• 如果 $t_j = 1$，则不需要将蛋添加到当前巢穴配置中。
• 如果 $t_j = 2$，则如果添加过程需要有限次移动，需将蛋实际添加。
• 如果 $t_j = 3$，则需计算有序对 $(x, y)$ 的数量，使得蛋 $(x, y)$ 可以放入巢穴 $x$，且过程最终会结束。实际中不添加任何蛋到配置中。

输出格式

对于每个第一类和第二类问题，输出 Yes 或 No，表示移动过程是否会结束。

对于每个第三类问题，输出所需有序对的数量。

样例

输入

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

输出

Yes
20
Yes
8
No
Yes
0
No

在题目示例中的初始蛋分布如下：巢穴 $1$ 中有蛋 $(1, 2)$，巢穴 $2$ 中有蛋 $(2, 4)$，巢穴 $5$ 中有蛋 $(5, 1)$，巢穴 $3$ 和 $4$ 中没有蛋。

蛋 $(1, 2)$ 可以添加，尽管树上已经有一个这样的蛋，这会导致已有蛋 $(1, 2)$ 被移动到另一个巢穴。

此外，在初始配置中可以添加 $5$ 个巢穴对应的 $10$ 个蛋中的任意一个，每个蛋可以放入其对应的两个巢穴中的任何一个，且对于任何添加的蛋和巢穴，过程都需要有限步数。因此，第二个问题的答案为 $20$。

在随后的问题中，蛋 $(1, 2)$ 将被实际添加，蛋的分布变为：巢穴 $1$ 中有蛋 $(1, 2)$，巢穴 $2$ 中也有蛋 $(1, 2)$，巢穴 $4$ 中有蛋 $(2, 4)$，巢穴 $5$ 中有蛋 $(5, 1)$。

此时，只能添加蛋 $(1, 3), (2, 3), (4, 3), (5, 3)$，且每个蛋仍可放入其对应的两个巢穴中，因此该问题的答案为 $8$。

蛋 $(4, 2)$ 无法添加到树上，因此巢穴状态不变。

添加蛋 $(5, 3)$ 需要 $5$ 次蛋的移动，之后无法再以有限步数添加任何新蛋。

数据范围与提示

设 $t_1$ 表示第一类问题的数量，$t_2$ 表示第二类问题的数量，$t_3$ 表示第三类问题的数量。

详细子任务附加限制及分值如下表所示。其中子任务 $0$ 是样例。