뻐꾸기

영국의 과학자들이 조류학을 연구하고 특이한 종류의 뻐꾸기 생활을 조사하기로 했다. 이들은 큰 나무를 한 그루 심고 그 위에 $n$개의 둥지를 두었다. 각 둥지에는 뻐꾸기가 한 마리씩 살고 있다. 조사에서는 주어진 둥지에 알을 하나 더 넣을 수 있는지 확인한다.

각 알은 둥지 두 개에만 놓을 수 있다. 알은 서로 다른 두 정수 $(x, y)$로 정해진다. 알 $(x, y)$는 둥지 $x$나 둥지 $y$에 놓을 수 있고, 다른 둥지에는 놓을 수 없다. $(x, y)$와 $(y, x)$는 같은 알이 아니다.

둥지 $x$에 알 $(x, y)$를 넣는 과정은 다음과 같다. 둥지 $x$가 비어 있으면 $(x, y)$가 그대로 남고 과정이 끝난다. 둥지 $x$에 이미 $(x, p)$ 알이 있다면, 뻐꾸기는 $(x, y)$를 둥지 $x$에 넣고 밀려난 $(x, p)$를 같은 방식으로 둥지 $p$에 넣으려고 한다. 이 과정이 계속된다.

과학자들의 질의에 답하라. 질의는 세 종류다.

1. (이론) 알 $(x, y)$를 둥지 $x$에 넣는 과정이 결국 멈추는가? 이 알은 실제로 추가되지 않으며 둥지의 상태도 바뀌지 않는다.
2. (실제) 알 $(x, y)$를 둥지 $x$에 넣는 과정이 결국 멈추는가? 멈추면 위의 과정에 따라 알이 실제로 추가된다.
3. (이론) 알 $(x, y)$를 둥지 $x$에 넣을 수 있고 과정이 결국 멈추는, 서로 다른 두 정수의 순서쌍 $(x, y)$는 몇 개인가? 각 쌍은 다른 쌍과 독립적으로 판정한다. 이 질의로는 알이 추가되지 않는다.

첫 줄에는 정수 $n$, $m$, $q$가 주어진다 ($2 \le n \le 200000$, $0 \le m \le n$, $1 \le q \le 600000$). $n$은 둥지의 개수, $m$은 이미 놓인 알의 개수, $q$는 질의의 개수다.

다음 $m$개의 줄에는 정수 $x_i$, $y_i$가 주어지며, 이는 둥지 $x_i$에 알 $(x_i, y_i)$가 있다는 뜻이다. 모든 $x_i$는 서로 다르며 모든 $i$에 대해 $x_i \ne 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$에 넣을 수 있고 과정이 유한한 쌍의 개수를 구한다. 이 질의에서는 알을 추가하지 않는다.

종류 1과 2의 각 질의에 대해 과정이 유한한지에 따라 Yes 또는 No를 출력한다. 종류 3의 각 질의에 대해서는 구하는 순서쌍의 개수를 출력한다.

$t_1$은 종류 1 질의의 개수, $t_2$는 종류 2 질의의 개수, $t_3$는 종류 3 질의의 개수를 뜻한다.

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

샘플의 초기 둥지 상태는 다음과 같다. 1번 둥지에는 알 $(1, 2)$가 있고, 2번 둥지에는 $(2, 4)$가 있으며, 5번 둥지에는 $(5, 1)$이 있다. 3번과 4번 둥지는 비어 있다.

같은 알 $(1, 2)$가 이미 있어도 $(1, 2)$를 추가할 수 있다. 이 경우 기존의 알 $(1, 2)$가 남은 둥지로 옮겨진다.

초기 상태에서는 다섯 개의 둥지로 된 나무에 가능한 알 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번 옮겨야 하고, 그 뒤에는 유한한 단계로 새 알을 추가할 수 없다.