Universal Cup Judging System

Universal Cup

時間限制: 2.5 s 記憶體限制: 1024 MB 總分: 100 可 Hack ✓
统计

$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)$(이전 연산에 의해 이미 삭제됨)을 삭제하도록 요청합니다.

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.