30755번 - Cuckoos 다국어

British scientists decided to study ornithology and to investigate the life of an extraordinary kind of cuckoos. They have planted a large tree and put $n$ nests on it, each of the nests is inhabited with one cuckoo. The investigation involves checking if it is possible to put an extra egg to the certain nest or not.

Each egg may be raised only in some two of the nests. Each egg is defined as an unordered pair of distinct integers $(x, y)$. The egg $(x, y)$ may be raised in any of the nests $x$ and $y$ and may not be raised in any of the other nests. Notice that egg $(x, y)$ не is the same as the egg $(y, x)$.

Now we will describe the process of putting an extra egg into a given nest. Suppose we want to put the egg $(x, y)$ to the nest $x$. If the nest $x$ is empty then $(x, y)$ remains in that nest and the process is over. Otherwise, if there is already an egg $(x, p)$ in the nest $x$, then cuckoo puts the egg $(x, y)$ to the nest $x$ and tries to put the egg $(x, p)$ to the nest $p$ in a similar manner, and the process continues.

You task is to answer several queries of the scientists. There are three types of queries:

1. \item(Theoretical) Will the process of putting of an egg $(x, y)$ to the nest $x$ eventually stop? Since the question is theoretical, this egg is not added actually, and the state of nests is not changed.
2. \item(Practical) Will the process of putting of an egg $(x, y)$ to the nest $x$ eventually stop? If the answer is positive, the egg is added according to the description of the process above.
3. \item(Theoretical) How many ordered pairs of distinct integers $(x, y)$ exist such that the egg $(x, y)$ may be put into the nest $x$ and the process will eventually stop? The answer for each pair is determined independently from any other pair.

The first line of the input contains three integers $n$, $m$, $q$, ($2 \leq n \leq 200\,000$, $0 \leq m \leq n$, $1 \leq q \leq 600\,000$), where $n$ is the number of nests, $m$ is the number of already given eggs, $q$ is the number of queries.

Each of the following $m$ lines contains two integers $x_i$, $y_i$ denoting that the nest $x_i$ contains an egg $(x_i, y_i)$. It is guaranteed that all $x_i$ are distinct and that $x_i \ne y_i$ for all $i$.

The following $q$ lines contain the queries. Queries are given in the order you have to perform them. The first number $t_j$ in the query line defines the type of the query.

If $t_j = 1$ or $t_j = 2$, then there are two distinct integers $x_j$ and $y_j$, defining an egg that appears in a corresponding query.

If $t_j = 1$, the egg should not be actually added to the current state.

If $t_j = 2$, the egg should be added if the process of putting an egg requires the finite number of egg transfers.

If $t_j = 3$, you are required to determine the number of ordered pairs $(x, y)$, such that the egg $(x, y)$ may be put to the nest $x$ and the process will be finite. No eggs are added to the state after this query.

For each query of the first and the second type output the only word "Yes" or "No" depending on the fact the process is finite or not.

For any query of the third type output the desired number of ordered pairs.

Let $t_1$ denote the number of queries of the first type, $t_2$ denote the number of queries of the second type and $t_3$ denote the number of queries of the third type.

• $t_1 \leq 2 \cdot 10^5$
• $t_2 \leq 2 \cdot 10^5$
• $t_3 \leq 2 \cdot 10^5$

Initial state of nests in the sample test is the following: the first nest contains the egg $(1, 2)$, the second nest contains the egg $(2, 4)$, the fifth nest contains the egg $(5, 1)$, the third an the fourth nests are empty.

The egg $(1, 2)$ may be added, despite the fact exactly the same egg is already present, this will transfer the existing egg $(1, 2)$ to the remaining nest.

Also, in the initial state it is possible to add any of the 10 possible eggs that exist for the tree with five nests, and each egg may be put in any of the two nests corresponding to it, such that the process will be finite. So, the answer for the second query is 20.

After the next query the egg $(1, 2)$ will be added, and the state of the eggs will be the following: the first nest contains an egg $(1, 2)$, the second also contains an egg $(1, 2)$, the fourth contains an egg $(2, 4)$ and the fifth contains an egg $(5, 1)$.

Now it is possible only to add the eggs $(1, 3)$, $(2, 3)$, $(4, 3)$ and $(5, 3)$, but still any of the specified eggs may be added to any of the corresponding nests, so the answer is 8.

An egg $(4, 2)$ may not be added to the tree in a finite number of steps, so the state of the nests won't change.

Adding an egg of $(5, 3)$ requires 5 egg transfers, and after that no new egg may be added in a finite number of steps.