Se te da un grafo no dirigido que consta de $n$ vértices y $m$ aristas. Los vértices están numerados desde cero: $0, 1, \dots, n - 1$. Debes procesar $q$ consultas. Cada consulta proporciona un par $(u, v)$ y te pide borrar la arista $(u, v)$ del grafo. Si no existe tal arista en el grafo (por ejemplo, si $u = v$), no hagas nada. Después de cada consulta, imprime si el grafo es conexo o no.
Entrada
La entrada contiene varios casos de prueba. La primera línea contiene un solo entero $t$ ($1 \le t \le 5 \cdot 10^5$), el número de casos de prueba. A continuación sigue la descripción de los casos de prueba.
La primera línea de cada caso de prueba contiene tres enteros $n$, $m$ y $q$ ($2 \le n \le 10^6$, $1 \le m, q \le 10^6$): el número de vértices, aristas y consultas, respectivamente.
Cada una de las siguientes $m$ líneas contiene dos enteros $u_i$ y $v_i$ ($0 \le u_i, v_i < n$), que representan una arista entre $u_i$ y $v_i$. No hay bucles ni aristas paralelas en el grafo.
Cada una de las siguientes $q$ líneas describe una consulta. Sin embargo, los parámetros de la consulta $u_j$ y $v_j$ no se proporcionan directamente. En su lugar, la $j$-ésima de estas líneas contiene dos enteros $a_j$ y $b_j$ ($0 \le a_j, b_j < n$). Supongamos que la respuesta a la $k$-ésima consulta es $c_k = 1$ si el grafo es conexo o $c_k = 0$ en caso contrario. Entonces $u_j$ y $v_j$ se generan de acuerdo con las fórmulas:
$$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 suma de todos los $n$, la suma de todos los $m$ y la suma de todos los $q$ en todos los casos de prueba no superan $10^6$.
Salida
Para cada caso de prueba, imprime $q$ líneas con los enteros $c_1, \dots, c_q$: las respuestas a las consultas.
Ejemplo
Entrada de ejemplo 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
Salida de ejemplo 1
0 0 1 1 0 0
Nota
En el primer caso de prueba, las consultas piden eliminar las aristas $(0, 0)$ (no existe) y $(0, 1)$.
En el segundo caso de prueba, las consultas piden eliminar las aristas $(0, 1)$, $(2, 0)$ (no existe), $(3, 0)$ y $(0, 3)$ (ya fue eliminada por la operación anterior).