Universal Cup Judging System

Universal Cup

حد الوقت: 2.5 s حد الذاكرة: 1024 MB مجموع النقاط: 100 قابلة للهجوم ✓
الإحصائيات

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

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.