Умова задачі
Звісно, це задача.
Це інтерактивна задача. Вам дано невідомий неорієнтований граф із $n$ вершинами та $m$ ребрами, без кратних ребер і петель. Щоразу ви можете поставити інтерактору таке запитання:
- Задано множину вершин $S \subseteq \{1, 2, \dots, n\}$, запитати, чи є ця множина вершин незалежною множиною.
Тут незалежна множина означає, що між будь-якими двома різними вершинами в множині $S$ немає ребра.
Ваша мета — визначити всю множину ребер графа, використавши не більше ніж $M = n + m(2 + \lceil\log_2 n\rceil)$ запитів.
Зверніть увагу, що значення $m$ заздалегідь невідоме, а інтерактор є адаптивним, тобто граф не зафіксований від самого початку, а динамічно змінюється залежно від ваших запитів.
Вхідні дані
Перший рядок містить ціле число $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
Примітка
Приклад демонструє інтерактивний процес індивідуальної перевірки існування кожного ребра.