Universal Cup Judging System

Universal Cup

Time Limit: 2.5 s Memory Limit: 1024 MB Total points: 100 Hackable ✓
Statistics

คุณได้รับกราฟไม่มีทิศทางที่ประกอบด้วยจุดยอด $n$ จุด และเส้นเชื่อม $m$ เส้น จุดยอดถูกกำหนดหมายเลขเริ่มจากศูนย์: $0, 1, \dots, n - 1$ คุณต้องประมวลผลคำถาม $q$ ข้อ แต่ละคำถามจะให้คู่อันดับ $(u, v)$ และขอให้คุณลบเส้นเชื่อม $(u, v)$ ออกจากกราฟ หากไม่มีเส้นเชื่อมดังกล่าวในกราฟ (ตัวอย่างเช่น หาก $u = v$) ก็ไม่ต้องทำอะไร หลังจากแต่ละคำถาม ให้พิมพ์ว่ากราฟเชื่อมต่อกัน (connected) หรือไม่

ข้อมูลนำเข้า

ข้อมูลนำเข้าประกอบด้วยหลายกรณีทดสอบ บรรทัดแรกประกอบด้วยจำนวนเต็มเดี่ยว $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$ ในกราฟไม่มีวงวนในตัวเอง (loop) และไม่มีเส้นเชื่อมขนาน (parallel edge)

แต่ละบรรทัดใน $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.