C. Нижний мир
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

Недавно открыв Нижний мир, Стив построил сеть из $$$n$$$ порталов в Нижний мир, каждый из которых находится в уникальной локации в его мире.

Каждый портал соединен в одном направлении с некоторым количеством (возможно, нулевым) других порталов. Чтобы не заблудиться, Стив построил сеть порталов так, чтобы не было последовательности прыжков через порталы, которая могла бы провести вас из одной локации обратно в неё; формально, сеть образует направленный ациклический граф.

Стив отказывается сообщать вам, какие порталы соединены с какими, но он позволит вам задавать запросы. В каждом запросе вы даете Стиву набор локаций $$$S = \{s_1, s_2, \ldots, s_k\}$$$ и начальную локацию $$$x \in S$$$. Стив определит самую длинную цепочку, начинающуюся с $$$x$$$, которая проходит только через локации в $$$S$$$, и сообщит вам количество локаций в ней. (Если из локации $$$x$$$ невозможно достичь любой локации в $$$S$$$, то Стив ответит $$$1$$$.)

Поскольку вы стремитесь получить достижение «Горящий тур», вы хотите найти любой путь, который посещает как можно больше локаций. Стив чувствует себя особенно щедрым и позволит вам сделать $$$2 \cdot n$$$ запросов, чтобы найти его.

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

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

Единственная строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$2 \le n \le 500$$$) — количество локаций.

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

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

Взаимодействие для каждого набора входных данных начинается с чтения целого числа $$$n$$$. Затем вы можете сделать до $$$2 \cdot n$$$ запросов.

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

  • $$$\texttt{?}\,\,x\,\,k\,\,s_1\,s_2\,\ldots\,s_k$$$

Жюри вернет ответ на запрос.

Когда вы найдете путь максимальной длины, выведите одну строку в следующем формате:

  • $$$\texttt{!}\,\,k\,\,v_1\,v_2\,\ldots\,v_k$$$

Это означает, что вы начинаете с портала $$$v_1$$$, затем прыгаете к $$$v_2$$$, затем к $$$v_3$$$ и так далее, заканчивая на $$$v_k$$$.

Обратите внимание, что вывод ответа не входит в лимит $$$2 \cdot n$$$ запросов.

После вывода каждого запроса не забудьте вывести перевод строки и сбросить буфер вывода$$$^{\text{∗}}$$$. В противном случае вы получите вердикт Решение «зависло».

На любом шаге взаимодействия, если вы считали $$$-1$$$ вместо корректных данных, ваше решение должно немедленно завершиться. Это означает, что ваше решение получит вердикт Неправильный ответ из-за некорректного запроса или любой другой ошибки. Если программа не завершится, вы можете получить любой вердикт, так как ваша программа продолжит чтение из закрытого потока.

Интерактор не адаптивен. Связи между порталами не меняются в процессе взаимодействия.

Взломы

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

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

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$2 \leq n \leq 500$$$) — количество локаций.

Затем выведите $$$n$$$ строк. $$$i$$$-я строка должна иметь формат $$$k_i\,v_1\,v_2\,\ldots\,v_{k_i}$$$ ($$$0 \le k_i \le n - 1$$$, $$$1 \le v_j \le n$$$, $$$v_j \ne i$$$), обозначая, что портал в локации $$$i$$$ соединен в одном направлении (ведет к) локациям $$$v_1, v_2, \ldots, v_{k_i}$$$. Данная сеть должна образовывать направленный ациклический граф.

Сумма $$$n^3$$$ по всем наборам входных данных не должна превосходить $$$500^3$$$.

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

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

3

3

2

1


2

1

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

? 1 4 1 2 3 4

? 3 3 4 3 2

? 5 2 1 5

? 2 2 2 4

! 4 5 1 4 2


? 1 2 1 2

? 2 2 1 2

! 1 1
Примечание

В первом наборе входных данных сеть порталов выглядит следующим образом:

  • Самый длинный путь, начинающийся в локации $$$1$$$ и проходящий только через $$$\{1, 2, 3, 4\}$$$, это путь $$$1 \rightarrow 4 \rightarrow 2$$$, который имеет $$$3$$$ различных локации.
  • Самый длинный путь, начинающийся в локации $$$3$$$ и проходящий только через $$$\{2, 3, 4\}$$$, это путь $$$3 \rightarrow 4 \rightarrow 2$$$, который имеет $$$3$$$ различных локации.
  • Самый длинный путь, начинающийся в локации $$$5$$$ и проходящий только через $$$\{1, 5\}$$$, это путь $$$5 \rightarrow 1$$$, который имеет $$$2$$$ различных локации.
  • Начиная с $$$2$$$ невозможно добраться до другой локации в $$$\{2, 4\}$$$, поэтому Стив отвечает $$$1$$$ на этот запрос.
Используя информацию из этих запросов, можно определить, что самый длинный путь — это $$$5 \rightarrow 1 \rightarrow 4 \rightarrow 2$$$.

Во втором наборе входных данных сеть порталов выглядит следующим образом:

Ни один из порталов не соединен с другим, поэтому самый длинный путь — это одна локация. Обратите внимание, что ! 1 2 также будет допустимым ответом.