Вам дан неориентированный граф, состоящий из $n$ вершин и $m$ рёбер. Вершины пронумерованы с нуля: $0, 1, \dots, n - 1$. Требуется обработать $q$ запросов. Каждый запрос задаёт пару $(u, v)$ и просит удалить ребро $(u, v)$ из графа. Если такого ребра в графе нет (например, если $u = v$), ничего делать не нужно. После каждого запроса выведите, является ли граф связным или нет.
Входные данные
Входные данные содержат несколько наборов входных данных. Первая строка содержит одно целое число $t$ ($1 \le t \le 5 \cdot 10^5$) — количество наборов входных данных. Далее следуют описания наборов.
Первая строка каждого набора содержит три целых числа $n$, $m$ и $q$ ($2 \le n \le 10^6$, $1 \le m, q \le 10^6$) — количество вершин, рёбер и запросов соответственно.
Каждая из следующих $m$ строк содержит два целых числа $u_i$ и $v_i$ ($0 \le u_i, v_i < n$), обозначающих ребро между $u_i$ и $v_i$. В графе нет петель и кратных рёбер.
Каждая из следующих $q$ строк описывает запрос. Однако параметры запроса $u_j$ и $v_j$ не заданы напрямую. Вместо этого $j$-я из этих строк содержит два целых числа $a_j$ и $b_j$ ($0 \le a_j, b_j < n$). Пусть ответ на $k$-й запрос равен $c_k = 1$, если граф связен, и $c_k = 0$ в противном случае. Тогда $u_j$ и $v_j$ вычисляются по формулам:
$$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.$$
Сумма всех $n$, сумма всех $m$ и сумма всех $q$ по всем наборам входных данных не превосходят $10^6$.
Выходные данные
Для каждого набора входных данных выведите $q$ строк с целыми числами $c_1, \dots, c_q$ — ответами на запросы.
Пример
Пример ввода 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
Пример вывода 1
0 0 1 1 0 0
Примечание
В первом наборе входных данных запросы требуют удалить рёбра $(0, 0)$ (его не существует) и $(0, 1)$.
Во втором наборе входных данных запросы требуют удалить рёбра $(0, 1)$, $(2, 0)$ (его не существует), $(3, 0)$ и $(0, 3)$ (оно уже было удалено предыдущей операцией).