G. NPC-челлендж
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это интерактивная задача.

Существует скрытое неориентированное дерево, состоящее из $$$n$$$ вершин. Чтобы восстановить это дерево, вы можете задавать запросы следующего вида:

  • Выберите последовательность различных вершин $$$a_1, a_2, \ldots, a_k$$$, где $$$k \ge 1$$$.

Интерактор обработает вашу последовательность и вернёт подмножество этих вершин $$$S$$$. Множество $$$S$$$ формируется следующим образом:

  • Изначально $$$S$$$ — пустое множество.

  • Интерактор обрабатывает вершины в точном порядке, в котором они указаны в вашей последовательности, от $$$a_1$$$ до $$$a_k$$$.

  • Для каждой вершины $$$a_i$$$, если $$$a_i$$$ не соединена ребром ни с одной вершиной, которая в данный момент находится в $$$S$$$, то $$$a_i$$$ добавляется в $$$S$$$. Иначе $$$a_i$$$ игнорируется.

  • После обработки всех $$$k$$$ вершин интерактор возвращает вам итоговое множество $$$S$$$. Множество $$$S$$$ представляется бинарной строкой $$$s$$$ длины $$$k$$$, где $$$s_i=\texttt{1}$$$ тогда и только тогда, когда $$$a_i \in S$$$.

Ваша задача — найти все $$$n-1$$$ рёбер скрытого дерева. Чтобы усложнить задачу, сумма $$$k$$$ по всем запросам не должна превосходить $$$30 \cdot n$$$.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 100$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

В первой строке каждого набора входных данных содержится целое число $$$n$$$ ($$$2 \le n \le 10^3$$$), обозначающее количество вершин в скрытом дереве.

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$10^3$$$.

Протокол взаимодействия

Чтобы сделать запрос, выведите строку в следующем формате:

  • $$$\mathtt{?}\;k\;a_1\;a_2\;\ldots\;a_k$$$ ($$$1 \le k \le n$$$, $$$1 \le a_i \le n$$$, $$$a_i \ne a_j$$$ для всех $$$1 \le i \lt j \le k$$$)

В ответ на запрос вы получите бинарную строку длины $$$k$$$, представляющую $$$S$$$.

Чтобы сообщить ответ, сначала выведите $$$\mathtt{!}$$$ на отдельной строке. Затем выведите $$$n-1$$$ строк, где $$$i$$$-я строка содержит два целых числа $$$u_i$$$ и $$$v_i$$$, обозначающие неориентированное ребро между вершинами $$$u_i$$$ и $$$v_i$$$. Рёбра можно выводить в любом порядке.

После этого переходите к следующему набору входных данных или завершайте работу, если это последний набор.

Интерактор не адаптивен. Это означает, что скрытое дерево фиксируется до начала всех запросов и не изменяется в ходе взаимодействия.

После вывода каждого запроса не забудьте вывести перевод строки и сбросить буфер вывода$$$^{\text{∗}}$$$. В противном случае вы получите вердикт Решение «зависло». На любом шаге взаимодействия, если вы считали $$$-1$$$ вместо корректных данных, ваше решение должно немедленно завершиться. Это означает, что ваше решение получит вердикт Неправильный ответ из-за некорректного запроса или любой другой ошибки. Если программа не завершится, вы можете получить любой вердикт, так как ваша программа продолжит чтение из закрытого потока.

Решение

Для взломов используйте следующий формат.

В первой строке должно быть указано одно целое число $$$t$$$ ($$$1 \le t \le 100$$$), обозначающее количество наборов входных данных.

В первой строке каждого набора должно быть указано целое число $$$n$$$ ($$$2 \le n \le 10^3$$$), обозначающее количество вершин в дереве.

Каждая из следующих $$$n-1$$$ строк должна содержать два целых числа $$$u$$$ и $$$v$$$ ($$$1 \le u,v \le n$$$, $$$u \ne v$$$), обозначающих ребро дерева. Необходимо гарантировать, что ребра образуют корректное дерево.

Сумма значений $$$n$$$ по всем тестовым примерам не должна превышать $$$10^3$$$.

$$$^{\text{∗}}$$$Чтобы сбросить буфер вывода, используйте:

  • fflush(stdout) или cout.flush() в C++;
  • sys.stdout.flush() в Python;
  • смотрите документацию для других языков.
Пример
Входные данные
2
2

10


5

101

10101
Выходные данные


? 2 1 2

!
2 1

? 3 1 2 5

? 5 5 3 4 2 1

!
3 5
1 2
3 2
2 4
Примечание

В первом наборе входных данных скрытое дерево состоит из $$$n=2$$$ вершин, и единственное ребро — $$$(1,2)$$$.

  • Для первого запроса $$$a=[1,2]$$$:

    • Обрабатывается вершина $$$1$$$. Сейчас $$$S$$$ пусто. Поскольку у $$$1$$$ нет соседей в $$$S$$$, она добавляется в $$$S$$$. $$$S$$$ становится $$$\{1\}$$$.

    • Обрабатывается вершина $$$2$$$. Её сосед, вершина $$$1$$$, уже находится в $$$S$$$. Следовательно, вершина $$$2$$$ игнорируется.

Во втором наборе входных данных скрытое дерево состоит из $$$n=5$$$ вершин. Рёбра: $$$(1, 2)$$$, $$$(2, 3)$$$, $$$(2, 4)$$$ и $$$(3, 5)$$$.

  • Для первого запроса $$$a=[1,2,5]$$$:

    • Обрабатывается вершина $$$1$$$. $$$S$$$ пусто. Она добавляется в $$$S$$$. $$$S$$$ становится $$$\{1\}$$$.

    • Обрабатывается вершина $$$2$$$. Она соединена ребром с вершиной $$$1 \in S$$$. Она игнорируется.

    • Обрабатывается вершина $$$5$$$. Её единственный сосед — вершина $$$3 \notin S$$$. Она добавляется в $$$S$$$. $$$S$$$ становится $$$\{1, 5\}$$$.

  • Для второго запроса $$$a=[5,3,4,2,1]$$$:

    • Обрабатывается вершина $$$5$$$. $$$S$$$ пусто. Она добавляется в $$$S$$$. $$$S$$$ становится $$$\{5\}$$$.

    • Обрабатывается вершина $$$3$$$. Она соединена ребром с вершиной $$$5 \in S$$$. Она игнорируется.

    • Обрабатывается вершина $$$4$$$. Её единственный сосед — вершина $$$2 \notin S$$$. Она добавляется в $$$S$$$. $$$S$$$ становится $$$\{4, 5\}$$$.

    • Обрабатывается вершина $$$2$$$. Она соединена ребром с вершиной $$$4 \in S$$$. Она игнорируется.

    • Обрабатывается вершина $$$1$$$. Её единственный сосед — вершина $$$2 \notin S$$$. Поскольку у неё нет соседей в $$$S$$$, она добавляется в $$$S$$$.