$n$개의 정점과 $m$개의 간선으로 이루어진 무방향 그래프가 주어집니다. 정점은 0부터 번호가 매겨져 있습니다: $0, 1, \dots, n - 1$. 당신은 $q$개의 쿼리를 처리해야 합니다. 각 쿼리는 순서쌍 $(u, v)$를 제공하며 그래프에서 간선 $(u, v)$를 지우도록 요청합니다. 만약 그래프에 그러한 간선이 없다면(예를 들어 $u = v$인 경우), 아무것도 하지 않습니다. 각 쿼리 직후에 그래프가 연결 그래프인지 아닌지를 출력하세요.
입력
입력은 여러 개의 테스트 케이스로 이루어져 있습니다. 첫 번째 줄에는 테스트 케이스의 개수를 나타내는 단일 정수 $t$($1 \le t \le 5 \cdot 10^5$)가 주어집니다. 이어서 테스트 케이스들의 설명이 주어집니다.
각 테스트 케이스의 첫 번째 줄에는 정점의 수, 간선의 수, 쿼리의 수를 나타내는 세 정수 $n$, $m$, $q$($2 \le n \le 10^6$, $1 \le m, q \le 10^6$)가 주어집니다.
다음 $m$개의 줄에는 각각 $u_i$와 $v_i$ 사이의 간선을 나타내는 두 정수 $u_i$와 $v_i$($0 \le u_i, v_i < n$)가 주어집니다. 그래프에는 자기 루프(loop)나 중복 간선(parallel edge)이 없습니다.
다음 $q$개의 줄에는 각각 하나의 쿼리가 설명됩니다. 하지만 쿼리 매개변수 $u_j$와 $v_j$는 직접 주어지지 않습니다. 대신 이 줄들 중 $j$번째 줄에는 두 정수 $a_j$와 $b_j$($0 \le a_j, b_j < n$)가 주어집니다. $k$번째 쿼리의 답을 그래프가 연결되어 있으면 $c_k = 1$, 그렇지 않으면 $c_k = 0$이라고 합시다. 그러면 $u_j$와 $v_j$는 다음 공식에 따라 생성됩니다:
$$u_j = (2^{j-2}c_1 + 2^{j-3}c_2 + \dots + 2^1 c_{j-2} + 2^0 c_{j-1} + a_j) \bmod n,$$
$$v_j = (3^{j-2}c_1 + 3^{j-3}c_2 + \dots + 3^1 c_{j-2} + 3^0 c_{j-1} + b_j) \bmod n.$$
모든 테스트 케이스에 걸쳐 모든 $n$의 합, 모든 $m$의 합, 모든 $q$의 합은 각각 $10^6$을 초과하지 않습니다.
출력
각 테스트 케이스마다 쿼리의 답인 정수 $c_1, \dots, c_q$를 $q$개의 줄에 걸쳐 출력합니다.
예제
예제 입력 1
2 3 1 2 0 1 0 0 0 1 4 4 4 0 1 1 2 2 3 0 3 0 1 1 3 0 0 2 3
예제 출력 1
0 0 1 1 0 0
노트
첫 번째 테스트 케이스에서 쿼리는 간선 $(0, 0)$(존재하지 않음)과 $(0, 1)$을 삭제하도록 요청합니다.
두 번째 테스트 케이스에서 쿼리는 간선 $(0, 1)$, $(2, 0)$(존재하지 않음), $(3, 0)$, 그리고 $(0, 3)$(이전 연산에 의해 이미 삭제됨)을 삭제하도록 요청합니다.