คุณได้รับกราฟไม่มีทิศทางที่ประกอบด้วยจุดยอด $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)$ (ซึ่งถูกลบไปแล้วโดยการดำเนินการก่อนหน้า)