Þér er gefið óstefnt net sem samanstendur af $n$ hnútum og $m$ leggjum. Hnútarnir eru númeraðir frá núlli: $0, 1, \dots, n - 1$. Þú átt að vinna úr $q$ fyrirspurnum. Hver fyrirspurn gefur par $(u, v)$ og biður þig um að eyða leggnum $(u, v)$ úr netinu. Ef enginn slíkur leggur er í netinu (til dæmis ef $u = v$), gerðu þá ekkert. Eftir hverja fyrirspurn skaltu prenta hvort netið sé samanhangandi eða ekki.
Inntak
Inntakið inniheldur nokkur prófunartilvik. Fyrsta línan inniheldur eina heiltölu $t$ ($1 \le t \le 5 \cdot 10^5$), fjölda prófunartilvika. Lýsingin á prófunartilvikunum fylgir á eftir.
Fyrsta línan í hverju prófunartilviki inniheldur þrjár heiltölur $n$, $m$ og $q$ ($2 \le n \le 10^6$, $1 \le m, q \le 10^6$): fjölda hnúta, leggja og fyrirspurna, í sömu röð.
Hver af næstu $m$ línum inniheldur tvær heiltölur $u_i$ og $v_i$ ($0 \le u_i, v_i < n$), sem tákna legg á milli $u_i$ og $v_i$. Það eru engar snörur og engir samsíða leggir í netinu.
Hver af næstu $q$ línum lýsir fyrirspurn. Viðföng fyrirspurnarinnar $u_j$ og $v_j$ eru hins vegar ekki gefin beint. Í staðinn inniheldur $j$-ta línan af þessum línum tvær heiltölur $a_j$ og $b_j$ ($0 \le a_j, b_j < n$). Gerum ráð fyrir að svarið við $k$-tu fyrirspurninni sé $c_k = 1$ ef netið er samanhangandi en $c_k = 0$ annars. Þá eru $u_j$ og $v_j$ búin til samkvæmt formúlunum:
$$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.$$
Summa allra $n$, summa allra $m$ og summa allra $q$ yfir öll prófunartilvik fara ekki yfir $10^6$.
Úttak
Fyrir hvert prófunartilvik skaltu prenta $q$ línur með heiltölunum $c_1, \dots, c_q$: svörunum við fyrirspurnunum.
Dæmi
Dæmi um inntak 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
Dæmi um úttak 1
0 0 1 1 0 0
Athugasemd
Í fyrsta prófunartilvikinu biðja fyrirspurnirnar um að eyða leggjunum $(0, 0)$ (hann er ekki til) og $(0, 1)$.
Í öðru prófunartilvikinu biðja fyrirspurnirnar um að eyða leggjunum $(0, 1)$, $(2, 0)$ (hann er ekki til), $(3, 0)$ og $(0, 3)$ (honum hefur þegar verið eytt í fyrri aðgerð).