โจทย์ข้อนี้เป็นโจทย์โต้ตอบแบบหลายรอบ (multi-pass, interactive problem) อย่าลืมล้างบัฟเฟอร์เอาต์พุตหลังจากการพิมพ์ทุกครั้ง คุณสามารถล้างเอาต์พุตได้โดยใช้:

• fflush(stdout) หรือ cout.flush() ใน C/C++;
• System.out.flush() ใน Java และ Kotlin;
• sys.stdout.flush() ใน Python.

แนวคิดของเกม วาดภาพประกอบโดย ChatGPT

ในเกม การจับคู่ออนไลน์ (online matching) แบบดั้งเดิม เส้นเชื่อมของกราฟจะถูกเปิดเผยทีละเส้น ทุกครั้งที่มีการแสดงเส้นเชื่อม คุณต้องตัดสินใจทันทีและไม่สามารถเปลี่ยนใจได้ว่าจะรวมเส้นเชื่อมนั้นไว้ในการจับคู่ของคุณหรือไม่ เป้าหมายของคุณคือการทำให้แน่ใจว่าไม่มีเส้นเชื่อมที่เลือกสองเส้นใดๆ ใช้จุดยอดร่วมกัน ในขณะที่ทำให้จำนวนเส้นเชื่อมที่เลือกทั้งหมดมีค่ามากที่สุด

คุณคือนักวิทยาศาสตร์คอมพิวเตอร์ผู้ทะเยอทะยานและกระหายชื่อเสียง อย่างที่คุณทราบดี การหาการจับคู่ขนาดใหญ่สุดในรูปแบบออนไลน์นั้นสามารถพิสูจน์ได้ว่าเป็นไปไม่ได้ด้วยความน่าจะเป็นสูง — แม้แต่กับคลาสของกราฟที่เรียบง่ายที่สุดอย่างกราฟสองส่วนก็ตาม ทว่าในจุดที่คนอื่นมองเห็นอุปสรรคพื้นฐาน คุณกลับมองเห็นโอกาสสู่ความรุ่งโรจน์ วันนี้คุณอ้างว่าได้ไขปัญหาเปิดที่มีมาอย่างยาวนานสำหรับกราฟต้นไม้ได้สำเร็จ และพร้อมที่จะเปิดตัวอัลกอริทึมสุดล้ำของคุณต่อชาวโลกแล้ว

มีปัญหาเพียงข้อเดียว: เมื่อวานนี้คุณพบข้อผิดพลาดในบทพิสูจน์ของคุณ และคุณยังไม่รู้ว่าจะแก้ไขมันอย่างไร ด้วยความที่ไม่ยอมทิ้งแสงไฟแห่งชื่อเสียง คุณจึงตัดสินใจเปลี่ยนการสาธิตของคุณให้กลายเป็นการแสดงมายากล — ผู้ช่วยของคุณซึ่งซ่อนตัวอยู่หลังเวทีจะส่งคำใบ้ เล็กๆ น้อยๆ เกี่ยวกับต้นไม้ทั้งต้นที่มี $n$ จุดยอดมาให้ก่อนที่เกมจะเริ่มต้นขึ้น

แผนเดิมของคุณนั้นเรียบง่าย: ให้ผู้ช่วยส่งคำตอบสำหรับคำถามแต่ละเส้นเชื่อมมาโดยตรง เพื่อการนี้ คุณได้ติดตั้งหูฟังลับที่สามารถรับสตริงฐานสองความยาว $(n - 1)$ ได้หนึ่งสาย แต่ผู้ชมกลับเคลือบแคลงใน "การค้นพบครั้งยิ่งใหญ่" ของคุณ เพื่อป้องกันการเตี๊ยมกันไว้ล่วงหน้า พวกเขาจึงเรียกร้องให้แสดงเส้นเชื่อมในลำดับสุ่มแบบสม่ำเสมอ — ซึ่งเป็นลำดับที่ทั้งคุณและผู้ช่วยของคุณไม่สามารถคาดเดาหรือควบคุมได้

เวทีพร้อมแล้ว แสงไฟส่องมาที่คุณ จงพิสูจน์คำกล่าวอ้างของคุณ — โดยไม่ต้องเปลี่ยนช่องสัญญาณ

โปรโตคอลการโต้ตอบ

โปรแกรมของคุณจะถูกรันสองครั้งในแต่ละชุดทดสอบ ในรอบ prepare โปรแกรมของคุณจะทำหน้าที่เป็นผู้ช่วย ในรอบ play โปรแกรมของคุณจะทำหน้าที่เป็น ตัวคุณ (นักมายากล) ไม่ว่าจะในรอบใด โปรแกรมของคุณจะถูกประเมินผลในรูปแบบกระบวนการโต้ตอบ

รอบเตรียมการ (Prepare Round)

บรรทัดแรกของข้อมูลนำเข้าประกอบด้วยคำว่า prepare บรรทัดที่สองประกอบด้วยจำนวนเต็ม $n$ ($2 \le n \le 500$) — จำนวนจุดยอด อีก $(n - 1)$ บรรทัดถัดไป แต่ละบรรทัดประกอบด้วยจำนวนเต็มสองจำนวน $u$ และ $v$ ($1 \le u, v \le n$, $u < v$) แทนเส้นเชื่อมไม่มีทิศทางระหว่าง $u$ และ $v$ ในต้นไม้

คุณต้องแสดงผลหนึ่งบรรทัดที่ประกอบด้วยสตริงฐานสอง $s$ ที่มีความยาวเท่ากับ $(n - 1)$ พอดี และประกอบด้วยอักขระ 0 และ 1 เท่านั้น นี่คือสตริงที่จะถูกส่งต่อไปยังรอบ play ที่สอง หากข้อมูลส่งออกของคุณไม่ตรงตามรูปแบบที่ต้องการ คุณจะได้รับผลการตัดสินเป็น Wrong Answer

รอบเล่นจริง (Play Round)

โปรแกรมของคุณจะถูกเริ่มต้นใหม่สำหรับรอบ play

บรรทัดแรกประกอบด้วยคำว่า play บรรทัดที่สองประกอบด้วยจำนวนเต็ม $n$ บรรทัดที่สามประกอบด้วยสตริงฐานสอง $s$ เหมือนกับที่คุณพิมพ์ไว้ในรอบ prepare ทุกประการ

หลังจากนั้น เกมจะเริ่มต้นขึ้นโดยมี $(n - 1)$ เทิร์น ในแต่ละเทิร์น จะมีหนึ่งบรรทัดที่ประกอบด้วยจำนวนเต็มสองจำนวน $u$ และ $v$ ($1 \le u, v \le n$, $u < v$) ส่งมาให้ เพื่อเป็นการตอบกลับ คุณต้องแสดงผลหนึ่งบรรทัดที่ประกอบด้วยคำว่า take หรือ ignore เส้นเชื่อมทั้งหมดในรอบแรกจะถูกส่งมาให้พอดีหนึ่งครั้ง และลำดับของเส้นเชื่อมจะถูกสุ่มอย่างสม่ำเสมอจากการเรียงสับเปลี่ยนที่เป็นไปได้ทั้งหมด $(n - 1)!$ แบบ

เมื่อมีการแสดงผลในรูปแบบที่ไม่ถูกต้อง เกมจะยุติลงทันทีโดยไม่มีข้อมูลเพิ่มเติมจากอินเทอร์แอกเตอร์

การประเมินความถูกต้อง

ให้ $M$ เป็นเซตของเส้นเชื่อมที่โปรแกรมของคุณเลือก ผลลัพธ์จะถือว่ายอมรับได้หากไม่มีจุดยอดใดเชื่อมต่อกับเส้นเชื่อมที่ถูกเลือกเกินหนึ่งเส้น และ $|M| = |M^*|$ เมื่อ $M^*$ คือการจับคู่ขนาดใหญ่สุดของกราฟ

มีชุดทดสอบทั้งหมด $50$ ชุดพอดี โดยไม่รวมชุดทดสอบตัวอย่าง เพื่อที่จะผ่านโจทย์ข้อนี้ โปรแกรมของคุณจะต้องทำงานถูกต้องในทุกชุดทดสอบ รวมถึงชุดทดสอบตัวอย่างด้วย

รับประกันว่าการสลับลำดับทั้งหมดถูกกำหนดตายตัวไว้ก่อนที่จะได้รับข้อมูลส่งออกจากโปรแกรม ความสุ่มจะถูกตรึงไว้สำหรับแต่ละชุดทดสอบโดยการกำหนดค่าเมล็ดพันธุ์ (seed) ของตัวสร้างตัวเลขสุ่มเทียม

มีเครื่องมือทดสอบเตรียมไว้ให้เพื่อช่วยในการพัฒนาและทดสอบโปรแกรมของคุณ

ตัวอย่าง

ตัวอย่างที่ 1, รอบที่ 1

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

prepare
3
1 2
1 3

ข้อมูลส่งออก

00

ตัวอย่างที่ 1, รอบที่ 2

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

play
3
00
1 3

1 2

ข้อมูลส่งออก

take

ignore

คำอธิบายตัวอย่างที่ 1

เนื่องจาก $|M^*| = 1$ การเลือกเส้นเชื่อมใดๆ ก็สามารถยอมรับได้ และคำใบ้สามารถเป็นอะไรก็ได้