คำอธิบายโจทย์
แน่นอน นี่คือโจทย์ปัญหา
นี่คือโจทย์ปัญหาแบบโต้ตอบ คุณได้รับกราฟไม่มีทิศทางที่ไม่ทราบโครงสร้างซึ่งมี $n$ จุดยอดและ $m$ เส้นเชื่อม โดยไม่มีเส้นเชื่อมขนานหรือวงวน ในแต่ละครั้ง คุณสามารถถามคำถามต่อไปนี้กับไลบรารีโต้ตอบได้:
- กำหนดเซตของจุดยอด $S \subseteq \{1, 2, \dots, n\}$ ถามว่าเซตของจุดยอดนี้เป็นเซตอิสระหรือไม่
ในที่นี้ เซตอิสระหมายความว่าไม่มีเส้นเชื่อมระหว่างจุดยอดสองจุดที่แตกต่างกันใดๆ ในเซต $S$
เป้าหมายของคุณคือการระบุเซตของเส้นเชื่อมทั้งหมดของกราฟโดยใช้คำถามไม่เกิน $M = n + m(2 + \lceil\log_2 n\rceil)$ ครั้ง
โปรดทราบว่าคุณไม่ทราบค่าของ $m$ ล่วงหน้า และไลบรารีโต้ตอบเป็นแบบปรับตัวได้ (adaptive) นั่นคือกราฟไม่ได้ถูกกำหนดตายตัวตั้งแต่ต้น แต่จะถูกปรับเปลี่ยนแบบไดนามิกตามคำถามของคุณ
ข้อมูลนำเข้า
บรรทัดแรกประกอบด้วยจำนวนเต็ม $T$ ($1 \le T \le 100$) แทนจำนวนกรณีทดสอบ
สำหรับแต่ละกรณีทดสอบ มีหนึ่งบรรทัดที่ประกอบด้วยจำนวนเต็ม $n$ ($1 \le n \le 500$) แทนจำนวนจุดยอดของกราฟไม่มีทิศทางที่ไม่ทราบโครงสร้าง
รับประกันว่าผลรวมของ $n$ ในทุกกรณีทดสอบไม่เกิน $500$, $0 \le m \le 500$ และผลรวมของ $m$ ไม่เกิน $500$
การโต้ตอบ
เมื่อคุณต้องการถามคำถาม ให้พิมพ์หนึ่งบรรทัด:
? k v_1 v_2 ... v_k
โดยที่ $k$ แทนขนาดของเซตจุดยอด และ $v_1, v_2, \dots, v_k$ คือหมายเลขของจุดยอดในเซตที่คุณกำลังถาม ซึ่งต้องแตกต่างกันทั้งหมด
ไลบรารีโต้ตอบจะคืนค่าจำนวนเต็มหนึ่งตัว: $1$ หากเซตของจุดยอดเป็นเซตอิสระ; $0$ ในกรณีอื่นๆ
เมื่อคุณระบุเส้นเชื่อมทั้งหมดของกราฟได้แล้ว ให้พิมพ์หนึ่งบรรทัด:
! m u_1 v_1 u_2 v_2 ... u_m v_m
โดยที่ $m$ คือจำนวนเส้นเชื่อมในกราฟไม่มีทิศทาง และ $(u_i, v_i)$ แทนเส้นเชื่อมหนึ่งในกราฟ คุณสามารถพิมพ์เส้นเชื่อมในลำดับใดก็ได้
หลังจากนั้น หากไม่มีกรณีทดสอบที่เหลืออยู่ โปรแกรมของคุณต้องหยุดทำงานทันที มิฉะนั้นจะต้องดำเนินการในกรณีทดสอบถัดไป
ตัวอย่าง
ข้อมูลนำเข้า 1
1 4 0 1 0 0 1 0
ข้อมูลส่งออก 1
? 2 1 2 ? 2 1 3 ? 2 1 4 ? 2 2 3 ? 2 2 4 ? 2 3 4 ! 4 1 2 2 3 3 4 1 4
คำอธิบาย
ตัวอย่างแสดงกระบวนการโต้ตอบของการถามแยกกันว่าแต่ละเส้นเชื่อมมีอยู่หรือไม่