Условие задачи
Конечно, это задача.
Это интерактивная задача. Вам дан неизвестный неориентированный граф с $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
Примечание
В примере показан интерактивный процесс индивидуальной проверки существования каждого ребра.