On vous donne un graphe non orienté composé de $n$ sommets et de $m$ arêtes. Les sommets sont numérotés à partir de zéro : $0, 1, \dots, n - 1$. Vous devez traiter $q$ requêtes. Chaque requête fournit une paire $(u, v)$ et vous demande d'effacer l'arête $(u, v)$ du graphe. S'il n'y a pas une telle arête dans le graphe (par exemple, si $u = v$), ne faites rien. Après chaque requête, affichez si le graphe est connexe ou non.
Entrée
L'entrée contient plusieurs cas de test. La première ligne contient un seul entier $t$ ($1 \le t \le 5 \cdot 10^5$), le nombre de cas de test. La description des cas de test suit.
La première ligne de chaque cas de test contient trois entiers $n$, $m$ et $q$ ($2 \le n \le 10^6$, $1 \le m, q \le 10^6$) : respectivement le nombre de sommets, d'arêtes et de requêtes.
Chacune des $m$ lignes suivantes contient deux entiers $u_i$ et $v_i$ ($0 \le u_i, v_i < n$), représentant une arête entre $u_i$ et $v_i$. Il n'y a ni boucles ni arêtes multiples dans le graphe.
Chacune des $q$ lignes suivantes décrit une requête. Cependant, les paramètres de la requête $u_j$ et $v_j$ ne sont pas fournis directement. À la place, la $j$-ième de ces lignes contient deux entiers $a_j$ et $b_j$ ($0 \le a_j, b_j < n$). Supposons que la réponse à la $k$-ième requête soit $c_k = 1$ si le graphe est connexe ou $c_k = 0$ sinon. Alors $u_j$ et $v_j$ sont générés selon les formules :
$$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 somme de tous les $n$, la somme de tous les $m$ et la somme de tous les $q$ sur l'ensemble des cas de test ne dépassent pas $10^6$.
Sortie
Pour chaque cas de test, affichez $q$ lignes avec les entiers $c_1, \dots, c_q$ : les réponses aux requêtes.
Exemple
Exemple d'entrée 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
Exemple de sortie 1
0 0 1 1 0 0
Note
Dans le premier cas de test, les requêtes demandent de supprimer les arêtes $(0, 0)$ (elle n'existe pas) et $(0, 1)$.
Dans le second cas de test, les requêtes demandent de supprimer les arêtes $(0, 1)$, $(2, 0)$ (elle n'existe pas), $(3, 0)$ et $(0, 3)$ (elle a déjà été supprimée par l'opération précédente).