Deskripsi Masalah
Tentu saja, ini adalah sebuah soal.
Ini adalah soal interaktif. Anda diberikan sebuah graf tak berarah yang tidak diketahui dengan $n$ verteks dan $m$ sisi, tanpa sisi ganda ataupun gelung (self-loop). Setiap kali, Anda dapat mengajukan pertanyaan berikut kepada pustaka interaksi:
- Diberikan sebuah himpunan verteks $S \subseteq \{1, 2, \dots, n\}$, tanyakan apakah himpunan verteks ini merupakan himpunan independen.
Di sini, himpunan independen berarti tidak ada sisi di antara dua verteks berbeda mana pun di dalam himpunan $S$.
Tujuan Anda adalah menentukan seluruh himpunan sisi dari graf tersebut menggunakan tidak lebih dari $M = n + m(2 + \lceil\log_2 n\rceil)$ pertanyaan.
Perhatikan bahwa Anda tidak mengetahui nilai $m$ sebelumnya, dan pustaka interaksi bersifat adaptif, yaitu graf tidak ditetapkan sejak awal, melainkan akan disesuaikan secara dinamis berdasarkan pertanyaan Anda.
Format Masukan
Baris pertama berisi sebuah bilangan bulat $T$ ($1 \le T \le 100$), yang menyatakan banyaknya kasus uji.
Untuk setiap kasus uji, satu baris berisi sebuah bilangan bulat $n$ ($1 \le n \le 500$), yang menyatakan banyaknya verteks pada graf tak berarah yang tidak diketahui.
Dijamin bahwa jumlah $n$ di semua kasus uji tidak melebihi $500$, $0 \le m \le 500$, dan jumlah $m$ tidak melebihi $500$.
Interaksi
Ketika Anda perlu mengajukan pertanyaan, keluarkan satu baris:
? k v_1 v_2 ... v_k
dengan $k$ menyatakan ukuran himpunan verteks, dan $v_1, v_2, \dots, v_k$ adalah indeks verteks dalam himpunan yang Anda tanyakan, semuanya saling berbeda.
Pustaka interaksi akan mengembalikan sebuah bilangan bulat: $1$ jika himpunan verteks tersebut adalah himpunan independen; $0$ jika sebaliknya.
Ketika Anda telah menentukan semua sisi dari graf, keluarkan satu baris:
! m u_1 v_1 u_2 v_2 ... u_m v_m
dengan $m$ adalah banyaknya sisi pada graf tak berarah, dan $(u_i, v_i)$ menyatakan sebuah sisi pada graf. Anda boleh mengeluarkan sisi-sisi tersebut dalam urutan apa pun.
Setelah itu, jika tidak ada kasus uji yang tersisa, program Anda harus segera berhenti; jika masih ada, program harus melanjutkan ke kasus uji berikutnya.
Contoh
Masukan 1
1 4 0 1 0 0 1 0
Keluaran 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
Catatan
Contoh menunjukkan proses interaktif menanyakan keberadaan setiap sisi satu per satu.