Sinulle annetaan suuntaamaton verkko, joka koostuu $n$ solmusta ja $m$ kaaresta. Solmut on numeroitu nollasta alkaen: $0, 1, \dots, n - 1$. Tehtäväsi on käsitellä $q$ kyselyä. Jokainen kysely antaa parin $(u, v)$ ja pyytää poistamaan kaaren $(u, v)$ verkosta. Jos tällaista kaarta ei ole verkossa (esimerkiksi jos $u = v$), älä tee mitään. Tulosta jokaisen kyselyn jälkeen, onko verkko yhtenäinen vai ei.
Syöte
Syöte sisältää useita testitapauksia. Ensimmäinen rivi sisältää yhden kokonaisluvun $t$ ($1 \le t \le 5 \cdot 10^5$), testitapausten lukumäärän. Seuraavaksi esitetään testitapausten kuvaukset.
Jokaisen testitapauksen ensimmäinen rivi sisältää kolme kokonaislukua $n$, $m$ ja $q$ ($2 \le n \le 10^6$, $1 \le m, q \le 10^6$): solmujen, kaarien ja kyselyiden lukumäärät tässä järjestyksessä.
Jokainen seuraavista $m$ rivistä sisältää kaksi kokonaislukua $u_i$ ja $v_i$ ($0 \le u_i, v_i < n$), jotka kuvaavat kaarta solmujen $u_i$ ja $v_i$ välillä. Verkossa ei ole silmukoita eikä rinnakkaisia kaaria.
Jokainen seuraavista $q$ rivistä kuvaa yhden kyselyn. Kyselyn parametreja $u_j$ ja $v_j$ ei kuitenkaan anneta suoraan. Sen sijaan $j$:s näistä riveistä sisältää kaksi kokonaislukua $a_j$ ja $b_j$ ($0 \le a_j, b_j < n$). Oletetaan, että vastaus $k$:nteen kyselyyn on $c_k = 1$, jos verkko on yhtenäinen, ja $c_k = 0$ muussa tapauksessa. Tällöin $u_j$ ja $v_j$ muodostetaan kaavoilla:
$$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.$$
Kaikkien lukujen $n$ summa, kaikkien lukujen $m$ summa ja kaikkien lukujen $q$ summa yli kaikkien testitapausten eivät ylitä lukua $10^6$.
Tuloste
Tulosta jokaista testitapausta kohden $q$ riviä, joilla ovat kokonaisluvut $c_1, \dots, c_q$: vastaukset kyselyihin.
Esimerkki
Esimerkkisyöte 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
Esimerkkituloste 1
0 0 1 1 0 0
Huomautus
Ensimmäisessä testitapauksessa kyselyt pyytävät poistamaan kaaret $(0, 0)$ (sitä ei ole olemassa) ja $(0, 1)$.
Toisessa testitapauksessa kyselyt pyytävät poistamaan kaaret $(0, 1)$, $(2, 0)$ (sitä ei ole olemassa), $(3, 0)$ ja $(0, 3)$ (se on jo poistettu edellisessä operaatiossa).