Universal Cup Judging System

Universal Cup

Süre Sınırı: 2.5 s Bellek Sınırı: 1024 MB Toplam puan: 100 Hack'lenebilir ✓
İstatistikler

給定一個由 $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.