32513번 - 동적 사이클 계산 쿼리

하나의 간선을 연결하는 간선이 없는 (즉, self loop가 없는) 무방향 그래프의 어떠한 간선 $e$에 대해, $e$를 포함하는 모든 간선 단순 사이클의 집합을 $C(e)$라고 하자. 간선 단순 사이클이란 한 정점에서 시작하여 시작 정점으로 돌아오며, 1개 이상의 간선을 가지고, 동일한 간선을 두번 이상 거치지 않는 경로를 의미한다. 정의에 따르면 단순 사이클에는 2개 이상의 서로 다른 정점이 포함된다. 시작 정점 이외의 다른 정점을 두번 이상 거치는 것도 허용된다는 것에 주의하라.

$n$개의 정점과 $m$개의 간선을 가지는 self loop가 없는 그래프 $G$가 주어진다. 각 정점은 1 이상 $n$ 이하의 서로 다른 번호가, 각 간선은 1 이상 $m$ 이하의 서로 다른 번호가 매겨져 있다. $e_i$ 를 $i$라는 번호가 매겨진 간선이라고 정의하자.

당신은 다음과 같은 쿼리를 대답해야 한다:

• 1 i j: $e_i, e_j$를 각각 그래프의 $i$번 간선과 $j$번 간선이라고 할 때, $C(e_i) = C(e_j)$ 가 성립하면 “1”, 아니면 “0” 를 출력하라. 두 간선 모두 이미 제거된 간선이 아님이 보장된다.
• 2 a b c d: 가장 마지막에 대답한 1번 쿼리의 결과가 “1” 일 경우 정점 $a$와 $b$를 잇는 간선을, “0” 일 경우 정점 $c$와 $d$를 잇는 간선을 추가한다. 이 쿼리가 $k$번째로 주어진 2번 쿼리일 경우, 추가된 간선은 $m+k$라는 번호가 매겨진다.
• 3 i j: 가장 마지막에 대답한 1번 쿼리의 결과가 “1” 일 경우 $e_i$를, “0” 일 경우 $e_j$를 그래프에서 제거한다. 두 간선 모두 이미 제거된 간선이 아님이 보장된다.

첫 쿼리가 1번 쿼리임이 보장된다. 초기 그래프의 간선들 및 2번 쿼리에 주어지는 간선들은 모두 서로 다른 정점을 잇는다. (다시 말해, 루프가 존재하지 않는다). 하지만 두 정점을 잇는 간선이 2개 이상일 수 있다.

파일의 첫째 줄에 테스트 케이스의 개수를 나타내는 자연수 $T$ 가 주어지고,

이후 차례로 $T$ 개의 테스트 케이스가 주어진다. ($1 \le T \le 36$)

각 테스트 케이스의 첫 줄에는 세 정수 n, m, q가 주어진다. ($2 \le n \le 50\,000, 1 \le m, q \le 50\,000$)

이후 m개의 줄에 초기 그래프의 간선이 주어진다. 각 간선은 간선이 잇는 두 끝점의 번호 u, v로 표현된다. ($1 \le u, v \le n, u \neq v$)

이후 q개의 줄에 쿼리가 주어진다. 쿼리의 형태는 위에서 설명한 것과 동일하다.

모든 테스트 케이스에 대해서 $n+m+q$의 합은 $3\,000\,000$ 을 넘지 않는다.

각 테스트 케이스마다 첫 줄에는 Case #$C$ 를 출력하여야 한다. 이때 $C$는 테스트 케이스의 번호이다.

다음 줄에 각 1번 쿼리에 대한 정답을 공백 없이 출력하라.