동적 사이클 계산 쿼리

자기 루프(self loop)가 없는 무방향 그래프의 간선 $e$에 대해, $e$를 포함하는 모든 간선 단순 사이클의 집합을 $C(e)$라고 하자. 간선 단순 사이클은 한 정점에서 출발해 같은 정점으로 돌아오는 경로이다. 간선을 1개 이상 가지며, 같은 간선을 두 번 이상 지나지 않는다. 정의에 따라 단순 사이클에는 서로 다른 정점이 2개 이상 포함된다. 시작 정점 이외의 정점을 두 번 이상 지나는 것은 허용된다.

정점 $n$개와 간선 $m$개를 가지고, 자기 루프가 없는 그래프 $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번 쿼리로 추가되는 간선은 모두 서로 다른 두 정점을 잇는다.

첫 줄에 테스트 케이스의 개수 $T$ ($1 \le T \le 36$)가 주어진다. 각 테스트 케이스의 첫 줄에는 정수 $n$, $m$, $q$가 주어진다 ($2 \le n \le 50000$, $1 \le m, q \le 50000$). 이어서 $m$개의 줄에 초기 간선의 두 끝점 $u$, $v$가 주어진다 ($1 \le u, v \le n$, $u \neq v$). 그다음 $q$개의 줄에 위에서 설명한 형식의 쿼리가 주어진다.

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

각 테스트 케이스마다 "Case #C"를 한 줄에 출력한다. 여기서 $C$는 테스트 케이스 번호이다. 다음 줄에는 1번 쿼리의 답을 입력 순서대로 공백 없이 이어 붙여 출력한다.