Deskripsi
Terdapat sebuah graf berarah dengan $n$ simpul yang dinomori dari $1$ hingga $n$. Untuk setiap simpul $1 \le i \le n$, derajat keluar dari simpul $i$ paling banyak satu; dengan demikian kita dapat mendeskripsikan graf tersebut menggunakan sebuah larik $p_i$, di mana $p_i = 0$ jika derajat keluar dari simpul $i$ adalah nol, dan selain itu $1 \le p_i \le n$, $p_i \ne i$, serta terdapat sisi berarah dari $i$ ke $p_i$. Tidak ada siklus berarah di dalam graf, sehingga dari simpul $i$ mana pun, lintasan yang terbentuk dengan terus berpindah ke simpul berikutnya sepanjang sisi berarah pada akhirnya akan berhenti di sebuah simpul dengan derajat keluar nol.
Pada awalnya, terdapat sebuah bidak kayu di salah satu simpul. Ketika Anda bertepuk tangan, jika bidak berada di simpul $i$ dengan $p_i$ tak nol, maka bidak akan berpindah ke simpul $p_i$; jika tidak, bidak tidak berpindah. Namun, Anda sama sekali tidak dapat melihat di mana bidak tersebut berada — satu-satunya operasi yang dapat Anda lakukan adalah memilih suatu himpunan bagian simpul, meletakkan bidak di salah satu simpul pilihan Anda, bertepuk tangan beberapa kali, dan mengamati apakah bidak berakhir di salah satu simpul pilihan Anda. Bahkan peletakan awal bidak dan banyaknya tepukan tangan dipilih oleh interaktor: Anda hanya dapat memilih himpunan bagian simpul, dan mengamati jumlah maksimum tepukan tangan sedemikian sehingga bidak dapat mulai di salah satu simpul pilihan Anda dan berakhir di salah satu simpul pilihan Anda.
Anda ingin menambahkan satu sisi dari $x$ ke $y$ ($1 \le x, y \le n$, $x \ne y$, dan $p_x = 0$, yaitu Anda dapat menetapkan $p_x = y$), sehingga Anda dapat bertepuk tangan lebih banyak kali lagi pada keseluruhan graf dibandingkan sebelumnya. Namun, penambahan sisi tersebut tetap tidak boleh menciptakan siklus berarah apa pun di dalam graf.
Temukan sisi mana pun yang dapat Anda tambahkan dengan melakukan kueri jumlah maksimum tepukan tangan pada paling banyak $n$ himpunan bagian simpul, atau tentukan bahwa mustahil untuk menambahkan sisi semacam itu.
Masukan
Baris pertama masukan berisi sebuah bilangan bulat $n$ ($1 \le n \le 1000$).
Interaksi
Untuk melakukan kueri, cetak satu baris berbentuk $\texttt{? } k \text{ } u_1 \text{ } u_2 \ldots u_k$, di mana $1 \le k \le n$, dan $1 \le u_i \le n$ adalah simpul-simpul yang saling berbeda dalam himpunan bagian pilihan Anda. Kemudian baca satu baris berisi sebuah bilangan bulat: jumlah maksimum tepukan tangan sedemikian sehingga bidak dapat mulai di salah satu simpul pilihan Anda dan berakhir di salah satu simpul pilihan Anda. Anda dapat melakukan paling banyak $n$ kueri.
Setelah Anda menentukan sisi yang ingin ditambahkan, cetak satu baris berbentuk $\texttt{! } x \text{ } y$, di mana $1 \le x, y \le n$ adalah titik-titik ujung dari sisi berarah yang ingin Anda tambahkan. Jika terdapat beberapa solusi, Anda boleh mencetak yang mana saja.
Jika mustahil untuk menambahkan sisi semacam itu, cetak $-1 \text{ -1}$ sebagai pengganti titik-titik ujung sisi.
Solusi Anda harus berhenti segera setelah mencetak jawaban.
Lakukan flush pada keluaran setelah setiap kueri yang Anda buat.
Interaktor tidak adaptif; graf sudah ditetapkan sebelumnya.
Contoh
6
2
1
2
? 4 1 2 3 4
? 2 5 6
? 3 4 5 6
! 5 1
Catatan
