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