Cuckoos

British scientists decided to study ornithology and investigate the life of an unusual kind of cuckoo. They planted a large tree and put $n$ nests on it, each inhabited by one cuckoo. The investigation checks whether an extra egg can be put into a given nest.

Each egg can be raised in only two of the nests. An egg is defined by a pair of distinct integers $(x, y)$. The egg $(x, y)$ may be raised in nest $x$ or nest $y$ and in no other nest. The egg $(x, y)$ is not the same as the egg $(y, x)$.

Putting an egg $(x, y)$ into nest $x$ works as follows. If nest $x$ is empty, $(x, y)$ stays there and the process ends. Otherwise, if nest $x$ already holds an egg $(x, p)$, the cuckoo puts $(x, y)$ into nest $x$ and tries to put the displaced egg $(x, p)$ into nest $p$ in the same way. The process continues.

Answer the scientists' queries. There are three types.

1. (Theoretical) Will putting an egg $(x, y)$ into nest $x$ eventually stop? This egg is not added, and the state of the nests does not change.
2. (Practical) Will putting an egg $(x, y)$ into nest $x$ eventually stop? If it does, the egg is added following the process above.
3. (Theoretical) How many ordered pairs of distinct integers $(x, y)$ exist such that the egg $(x, y)$ can be put into nest $x$ and the process eventually stops? Each pair is judged independently of the others. No egg is added by this query.

The first line contains three integers $n$, $m$, $q$ ($2 \le n \le 200000$, $0 \le m \le n$, $1 \le q \le 600000$), where $n$ is the number of nests, $m$ is the number of eggs already placed, and $q$ is the number of queries.

Each of the next $m$ lines contains two integers $x_i$ and $y_i$, meaning nest $x_i$ contains the egg $(x_i, y_i)$. All $x_i$ are distinct, and $x_i \ne y_i$ for all $i$.

The next $q$ lines are the queries, in the order they must be processed. The first number $t_j$ is the query type. For $t_j = 1$ or $t_j = 2$, two distinct integers $x_j$ and $y_j$ follow, describing the egg in that query. A query of type 1 does not add the egg. A query of type 2 adds the egg if the process requires a finite number of egg transfers. For $t_j = 3$, the query asks for the count described above, and no egg is added.

For each query of type 1 or type 2, print Yes if the process is finite and No otherwise. For each query of type 3, print the number of ordered pairs.

Let $t_1$ denote the number of queries of type 1, $t_2$ the number of queries of type 2, and $t_3$ the number of queries of type 3.

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

The initial state of the nests in the sample is as follows. Nest 1 contains the egg $(1, 2)$, nest 2 contains the egg $(2, 4)$, nest 5 contains the egg $(5, 1)$, and nests 3 and 4 are empty.

The egg $(1, 2)$ can be added even though the same egg is already present. This transfers the existing egg $(1, 2)$ to the remaining nest.

In the initial state, any of the 10 possible eggs for a tree with five nests can be added, and each egg can go into either of its two nests, so the process is finite. The answer to the second query is 20.

After the next query adds the egg $(1, 2)$, nest 1 contains an egg $(1, 2)$, nest 2 contains an egg $(1, 2)$, nest 4 contains the egg $(2, 4)$, and nest 5 contains the egg $(5, 1)$. Now only the eggs $(1, 3)$, $(2, 3)$, $(4, 3)$, and $(5, 3)$ can be added. Each of them can still go into either of its corresponding nests, so the answer is 8.

The egg $(4, 2)$ cannot be added in a finite number of steps, so the state of the nests does not change.

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