คำอธิบาย
มีกราฟระบุทิศทางที่มี $n$ จุดยอด หมายเลข $1$ ถึง $n$ สำหรับแต่ละจุดยอด $1 \le i \le n$ ดีกรีออกของจุดยอด $i$ มีค่าไม่เกินหนึ่ง ดังนั้นเราจึงสามารถอธิบายกราฟด้วยอาร์เรย์ $p_i$ โดยที่ $p_i = 0$ หากดีกรีออกของจุดยอด $i$ เป็นศูนย์ และมิฉะนั้น $1 \le p_i \le n$, $p_i \ne i$ และมีเส้นเชื่อมระบุทิศทางจาก $i$ ไปยัง $p_i$ ในกราฟไม่มีวัฏจักรระบุทิศทาง ดังนั้นจากจุดยอด $i$ ใดๆ เส้นทางที่เกิดจากการเคลื่อนที่ไปยังจุดยอดถัดไปตามเส้นเชื่อมระบุทิศทางซ้ำๆ จะสิ้นสุดลงที่จุดยอดที่มีดีกรีออกเป็นศูนย์ในที่สุด
ในตอนแรก มีหมากฮอสไม้วางอยู่บนจุดยอดจุดหนึ่ง เมื่อคุณปรบมือ หากหมากฮอสอยู่บนจุดยอด $i$ ที่มี $p_i$ ไม่เป็นศูนย์ มันจะเคลื่อนที่ไปยังจุดยอด $p_i$ มิฉะนั้นมันจะไม่เคลื่อนที่ อย่างไรก็ตาม คุณไม่สามารถมองเห็นได้เลยว่าหมากฮอสอยู่ที่ไหน — การดำเนินการเดียวที่คุณทำได้คือเลือกสับเซตของจุดยอด วางหมากฮอสลงบนจุดยอดหนึ่งในกลุ่มที่คุณเลือก ปรบมือจำนวนหนึ่ง แล้วสังเกตว่าหมากฮอสไปหยุดอยู่ที่จุดยอดหนึ่งในกลุ่มที่คุณเลือกหรือไม่ แม้แต่ตำแหน่งเริ่มต้นของหมากฮอสและจำนวนครั้งที่คุณปรบมือก็ถูกเลือกโดยอินเทอร์แอกเตอร์: คุณทำได้เพียงเลือกสับเซตของจุดยอด และสังเกตจำนวนครั้งสูงสุดที่คุณสามารถปรบมือได้โดยที่หมากฮอสสามารถเริ่มต้นบนจุดยอดหนึ่งในกลุ่มที่คุณเลือกและจบลงบนจุดยอดหนึ่งในกลุ่มที่คุณเลือก
คุณต้องการเพิ่มเส้นเชื่อมเพียงเส้นเดียวจาก $x$ ไปยัง $y$ ($1 \le x, y \le n$, $x \ne y$ และ $p_x = 0$ กล่าวคือคุณสามารถกำหนดให้ $p_x = y$) เพื่อให้คุณสามารถปรบมือบนกราฟทั้งหมดได้จำนวนครั้งมากกว่าเดิม อย่างไรก็ตาม การเพิ่มเส้นเชื่อมจะต้องไม่ทำให้เกิดวัฏจักรระบุทิศทางใดๆ ในกราฟ
จงหาเส้นเชื่อมดังกล่าวเส้นใดก็ได้ที่คุณสามารถเพิ่มได้ โดยการสอบถามจำนวนครั้งสูงสุดที่คุณสามารถปรบมือได้บนสับเซตของจุดยอดไม่เกิน $n$ สับเซต หรือระบุว่าเป็นไปไม่ได้ที่จะเพิ่มเส้นเชื่อมดังกล่าว
ข้อมูลนำเข้า
บรรทัดแรกของข้อมูลนำเข้าประกอบด้วยจำนวนเต็ม $n$ ($1 \le n \le 1000$) เพียงตัวเดียว
การโต้ตอบ
ในการสอบถามแต่ละครั้ง ให้พิมพ์บรรทัดเดียวในรูปแบบ $\texttt{? } k \text{ } u_1 \text{ } u_2 \ldots u_k$ โดยที่ $1 \le k \le n$ และ $1 \le u_i \le n$ คือจุดยอดที่แตกต่างกันทั้งหมดในสับเซตที่คุณเลือก จากนั้นให้อ่านบรรทัดเดียวที่มีจำนวนเต็มหนึ่งตัว: จำนวนครั้งสูงสุดที่คุณสามารถปรบมือได้โดยที่หมากฮอสสามารถเริ่มต้นบนจุดยอดหนึ่งในกลุ่มที่คุณเลือกและจบลงบนจุดยอดหนึ่งในกลุ่มที่คุณเลือก คุณสามารถสอบถามได้ไม่เกิน $n$ ครั้ง
หลังจากที่คุณระบุเส้นเชื่อมที่คุณต้องการเพิ่มได้แล้ว ให้พิมพ์บรรทัดเดียวในรูปแบบ $\texttt{! } x \text{ } y$ โดยที่ $1 \le x, y \le n$ คือจุดปลายของเส้นเชื่อมระบุทิศทางที่คุณต้องการเพิ่ม หากมีคำตอบได้หลายแบบ คุณสามารถแสดงคำตอบใดก็ได้
หากเป็นไปไม่ได้ที่จะเพิ่มเส้นเชื่อมดังกล่าว ให้พิมพ์ $-1 \text{ -1}$ แทนจุดปลายของเส้นเชื่อม
โปรแกรมของคุณต้องหยุดทำงานทันทีหลังจากแสดงคำตอบแล้ว
ให้ล้างบัฟเฟอร์ข้อมูลส่งออก (flush) หลังจากการสอบถามแต่ละครั้ง
อินเทอร์แอกเตอร์ไม่ได้ปรับเปลี่ยนตามคำถาม (not adaptive); กราฟถูกกำหนดไว้ล่วงหน้าแล้ว
ตัวอย่าง
6
2
1
2
? 4 1 2 3 4
? 2 5 6
? 3 4 5 6
! 5 1
หมายเหตุ
