Вам дано неорієнтований граф, що складається з $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)$ (його вже було видалено попередньою операцією).