Ti viene dato un grafo non orientato composto da $n$ vertici e $m$ archi. I vertici sono numerati a partire da zero: $0, 1, \dots, n - 1$. Devi elaborare $q$ query. Ogni query fornisce una coppia $(u, v)$ e ti chiede di cancellare l'arco $(u, v)$ dal grafo. Se un tale arco non è presente nel grafo (ad esempio, se $u = v$), non fare nulla. Dopo ogni query, stampa se il grafo è connesso oppure no.
Input
L'input contiene diversi casi di test. La prima riga contiene un singolo intero $t$ ($1 \le t \le 5 \cdot 10^5$), il numero di casi di test. Segue la descrizione dei casi di test.
La prima riga di ogni caso di test contiene tre interi $n$, $m$ e $q$ ($2 \le n \le 10^6$, $1 \le m, q \le 10^6$): rispettivamente il numero di vertici, di archi e di query.
Ciascuna delle successive $m$ righe contiene due interi $u_i$ e $v_i$ ($0 \le u_i, v_i < n$), che rappresentano un arco tra $u_i$ e $v_i$. Nel grafo non ci sono cappi né archi paralleli.
Ciascuna delle successive $q$ righe descrive una query. Tuttavia, i parametri della query $u_j$ e $v_j$ non vengono forniti direttamente. Al contrario, la $j$-esima di queste righe contiene due interi $a_j$ e $b_j$ ($0 \le a_j, b_j < n$). Supponiamo che la risposta alla $k$-esima query sia $c_k = 1$ se il grafo è connesso o $c_k = 0$ altrimenti. Allora $u_j$ e $v_j$ sono generati secondo le formule:
$$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.$$
La somma di tutti gli $n$, la somma di tutti gli $m$ e la somma di tutti i $q$ su tutti i casi di test non superano $10^6$.
Output
Per ogni caso di test, stampa $q$ righe con gli interi $c_1, \dots, c_q$: le risposte alle query.
Esempio
Input di esempio 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
Output di esempio 1
0 0 1 1 0 0
Nota
Nel primo caso di test, le query chiedono di eliminare gli archi $(0, 0)$ (non esiste) e $(0, 1)$.
Nel secondo caso di test, le query chiedono di eliminare gli archi $(0, 1)$, $(2, 0)$ (non esiste), $(3, 0)$ e $(0, 3)$ (è già stato eliminato dall'operazione precedente).