Universal Cup Judging System

Universal Cup

Time Limit: 2.5 s Memory Limit: 1024 MB Total points: 100 Hackable ✓
Statistics

Gegeben ist ein ungerichteter Graph, der aus $n$ Knoten und $m$ Kanten besteht. Die Knoten sind ab null nummeriert: $0, 1, \dots, n - 1$. Du musst $q$ Anfragen verarbeiten. Jede Anfrage gibt ein Paar $(u, v)$ vor und fordert dich auf, die Kante $(u, v)$ aus dem Graphen zu löschen. Falls es keine solche Kante im Graphen gibt (zum Beispiel wenn $u = v$ gilt), tue nichts. Gib nach jeder Anfrage aus, ob der Graph zusammenhängend ist oder nicht.

Eingabe

Die Eingabe enthält mehrere Testfälle. Die erste Zeile enthält eine einzelne ganze Zahl $t$ ($1 \le t \le 5 \cdot 10^5$), die Anzahl der Testfälle. Es folgt die Beschreibung der Testfälle.

Die erste Zeile jedes Testfalls enthält drei ganze Zahlen $n$, $m$ und $q$ ($2 \le n \le 10^6$, $1 \le m, q \le 10^6$): die Anzahl der Knoten, Kanten bzw. Anfragen.

Jede der nächsten $m$ Zeilen enthält zwei ganze Zahlen $u_i$ und $v_i$ ($0 \le u_i, v_i < n$), die eine Kante zwischen $u_i$ und $v_i$ darstellen. Es gibt keine Schleifen und keine Mehrfachkanten im Graphen.

Jede der nächsten $q$ Zeilen beschreibt eine Anfrage. Allerdings werden die Anfrageparameter $u_j$ und $v_j$ nicht direkt angegeben. Stattdessen enthält die $j$-te dieser Zeilen zwei ganze Zahlen $a_j$ und $b_j$ ($0 \le a_j, b_j < n$). Angenommen, die Antwort auf die $k$-te Anfrage ist $c_k = 1$, falls der Graph zusammenhängend ist, oder $c_k = 0$ andernfalls. Dann werden $u_j$ und $v_j$ gemäß den folgenden Formeln erzeugt:

$$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.$$

Die Summe aller $n$, die Summe aller $m$ und die Summe aller $q$ über alle Testfälle hinweg überschreiten jeweils nicht $10^6$.

Ausgabe

Gib für jeden Testfall $q$ Zeilen mit den ganzen Zahlen $c_1, \dots, c_q$ aus: die Antworten auf die Anfragen.

Beispiel

Beispieleingabe 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

Beispielausgabe 1

0
0
1
1
0
0

Hinweis

Im ersten Testfall fordern die Anfragen das Löschen der Kanten $(0, 0)$ (sie existiert nicht) und $(0, 1)$.

Im zweiten Testfall fordern die Anfragen das Löschen der Kanten $(0, 1)$, $(2, 0)$ (sie existiert nicht), $(3, 0)$ und $(0, 3)$ (sie wurde bereits durch die vorherige Operation gelöscht).

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.