Du får oppgitt en urettet graf som består av $n$ noder og $m$ kanter. Nodene er nummerert fra null: $0, 1, \dots, n - 1$. Du skal behandle $q$ spørringer. Hver spørring oppgir et par $(u, v)$ og ber deg om å fjerne kanten $(u, v)$ fra grafen. Hvis det ikke finnes en slik kant i grafen (for eksempel hvis $u = v$), gjør du ingenting. Etter hver spørring skal du skrive ut om grafen er sammenhengende eller ikke.
Inndata
Inndataene inneholder flere testtilfeller. Den første linjen inneholder et enkelt heltall $t$ ($1 \le t \le 5 \cdot 10^5$), antallet testtilfeller. Beskrivelsen av testtilfellene følger.
Den første linjen i hvert testtilfelle inneholder tre heltall $n$, $m$ og $q$ ($2 \le n \le 10^6$, $1 \le m, q \le 10^6$): antallet henholdsvis noder, kanter og spørringer.
Hver av de neste $m$ linjene inneholder to heltall $u_i$ og $v_i$ ($0 \le u_i, v_i < n$), som representerer en kant mellom $u_i$ og $v_i$. Det er ingen løkker og ingen parallelle kanter i grafen.
Hver av de neste $q$ linjene beskriver en spørring. Spørringsparametrene $u_j$ og $v_j$ oppgis imidlertid ikke direkte. I stedet inneholder den $j$-te av disse linjene to heltall $a_j$ og $b_j$ ($0 \le a_j, b_j < n$). Anta at svaret på den $k$-te spørringen er $c_k = 1$ hvis grafen er sammenhengende, eller $c_k = 0$ ellers. Da genereres $u_j$ og $v_j$ etter formlene:
$$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.$$
Summen av alle $n$, summen av alle $m$ og summen av alle $q$ over alle testtilfellene overstiger ikke $10^6$.
Utdata
For hvert testtilfelle skal du skrive ut $q$ linjer med heltallene $c_1, \dots, c_q$: svarene på spørringene.
Eksempel
Eksempelinndata 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
Eksempelutdata 1
0 0 1 1 0 0
Merknad
I det første testtilfellet ber spørringene om å slette kantene $(0, 0)$ (den finnes ikke) og $(0, 1)$.
I det andre testtilfellet ber spørringene om å slette kantene $(0, 1)$, $(2, 0)$ (den finnes ikke), $(3, 0)$ og $(0, 3)$ (den er allerede slettet av den forrige operasjonen).