Universal Cup Judging System

Universal Cup

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

Dany jest graf nieskierowany składający się z $n$ wierzchołków i $m$ krawędzi. Wierzchołki są ponumerowane od zera: $0, 1, \dots, n - 1$. Twoim zadaniem jest przetworzenie $q$ zapytań. Każde zapytanie podaje parę $(u, v)$ i prosi o usunięcie krawędzi $(u, v)$ z grafu. Jeśli takiej krawędzi nie ma w grafie (na przykład gdy $u = v$), nie rób nic. Po każdym zapytaniu wypisz, czy graf jest spójny, czy nie.

Wejście

Wejście zawiera wiele przypadków testowych. Pierwszy wiersz zawiera jedną liczbę całkowitą $t$ ($1 \le t \le 5 \cdot 10^5$), oznaczającą liczbę przypadków testowych. Następnie podane są opisy kolejnych przypadków testowych.

Pierwszy wiersz każdego przypadku testowego zawiera trzy liczby całkowite $n$, $m$ oraz $q$ ($2 \le n \le 10^6$, $1 \le m, q \le 10^6$): odpowiednio liczbę wierzchołków, krawędzi oraz zapytań.

Każdy z kolejnych $m$ wierszy zawiera dwie liczby całkowite $u_i$ oraz $v_i$ ($0 \le u_i, v_i < n$), reprezentujące krawędź między $u_i$ a $v_i$. W grafie nie ma pętli ani krawędzi wielokrotnych.

Każdy z kolejnych $q$ wierszy opisuje zapytanie. Parametry zapytania $u_j$ oraz $v_j$ nie są jednak podane bezpośrednio. Zamiast tego $j$-ty z tych wierszy zawiera dwie liczby całkowite $a_j$ oraz $b_j$ ($0 \le a_j, b_j < n$). Załóżmy, że odpowiedzią na $k$-te zapytanie jest $c_k = 1$, jeśli graf jest spójny, lub $c_k = 0$ w przeciwnym razie. Wówczas $u_j$ oraz $v_j$ są generowane według wzorów:

$$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.$$

Suma wszystkich $n$, suma wszystkich $m$ oraz suma wszystkich $q$ po wszystkich przypadkach testowych nie przekraczają $10^6$.

Wyjście

Dla każdego przypadku testowego wypisz $q$ wierszy z liczbami całkowitymi $c_1, \dots, c_q$: odpowiedziami na kolejne zapytania.

Przykład

Przykładowe wejście 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

Przykładowe wyjście 1

0
0
1
1
0
0

Uwaga

W pierwszym przypadku testowym zapytania proszą o usunięcie krawędzi $(0, 0)$ (nie istnieje) oraz $(0, 1)$.

W drugim przypadku testowym zapytania proszą o usunięcie krawędzi $(0, 1)$, $(2, 0)$ (nie istnieje), $(3, 0)$ oraz $(0, 3)$ (została już usunięta przez poprzednią operację).

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.