F. Теорема Костяныча
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

Костяныч загадал полный неориентированный граф$$$^{\dagger}$$$ на $$$n$$$ вершинах, после чего удалил из него ровно $$$(n - 2)$$$ ребра. Вы можете делать запросы следующего вида:

  • «? $$$d$$$» — Костяныч сообщает вам номер вершины $$$v$$$ со степенью хотя бы $$$d$$$. Из всех возможных таких вершин он выбирает вершину с минимальной степенью, если таких несколько, то с минимальным номером. Также он сообщает вам номер другой вершины из графа, с которой $$$v$$$ не соединена ребром (если такой не нашлось, то сообщается $$$0$$$). Из всех возможных таких вершин он выбирает вершину с минимальным номером. Затем он удаляет вершину $$$v$$$ и все выходящие из неё рёбра. Если требуемой вершины $$$v$$$ не нашлось, то сообщается «$$$0\ 0$$$».

Найдите в исходном графе гамильтонов путь$$$^{\ddagger}$$$ за не более чем $$$n$$$ запросов. Можно показать, что при данных ограничениях гамильтонов путь всегда существует.

$$$^{\dagger}$$$Полным неориентированным графом называется граф, в котором между любой парой различных вершин есть ровно одно неориентированное ребро. Таким образом, полный неориентированный граф на $$$n$$$ вершинах содержит $$$\frac{n(n-1)}{2}$$$ рёбер.

$$$^{\ddagger}$$$Гамильтоновым путём в графе называется путь, который проходит через каждую вершину ровно один раз.

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

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

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

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

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

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

Затем вы можете сделать не более $$$n$$$ запросов.

Чтобы сделать запрос, выведите строку в формате «? $$$d$$$» (без кавычек) ($$$0 \le d \le n - 1$$$). После каждого запроса считайте два целых числа — ответ на ваш запрос.

Когда вы будете готовы сообщить ответ, выведите строку в формате «! $$$v_1\ v_2 \ldots v_n$$$» (без кавычек) — вершины в порядке их следования в гамильтоновом пути. Вывод ответа не считается как один из $$$n$$$ запросов. После решения одного набора входных данных программа должна сразу же переходить к следующему. После решения всех наборов входных данных программа должна быть немедленно завершена.

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

После вывода запроса не забудьте вывести перевод строки и сбросить буфер вывода. В противном случае вы получите вердикт Решение «зависло». Для сброса буфера используйте:

  • fflush(stdout) или cout.flush() в C++;
  • System.out.flush() в Java;
  • flush(output) в Pascal;
  • stdout.flush() в Python;
  • смотрите документацию для других языков.

Интерактор неадаптивный. Граф не меняется в процессе взаимодействия.

Взломы

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

Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 1000$$$) — количество наборов входных данных.

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

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

Сумма $$$n$$$ по всем наборам входных данных не должна превышать $$$10^5$$$.

Пример
Входные данные
3
4

0 0

1 4

2 3

4

1 0

4 2

2

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


? 3

? 2

? 1

! 4 3 1 2

? 3

? 0

! 4 1 2 3

? 0

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

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

Рассмотрим запросы:

  • Вершины степени хотя бы $$$3$$$ в графе нет, поэтому сообщается «$$$0\ 0$$$».
  • Есть четыре вершины степени хотя бы $$$2$$$, и все они имеют степень ровно $$$2$$$: $$$1$$$, $$$2$$$, $$$3$$$, $$$4$$$. Сообщается вершина $$$1$$$, потому что она имеет минимальный номер, и вершина $$$4$$$, потому что только она не соединена с вершиной $$$1$$$. После этого вершина $$$1$$$ удаляется из графа.
  • Есть три вершины степени хотя бы $$$1$$$, из них минимальную степень $$$1$$$ имеют вершины $$$2$$$ и $$$3$$$ (вершина $$$4$$$ имеет степень $$$2$$$). Сообщается вершина $$$2$$$, потому что она имеет минимальный номер, и вершина $$$3$$$, потому что только она не соединена с вершиной $$$2$$$. После этого вершина $$$2$$$ удаляется из графа.

Путь $$$4 - 3 - 1 - 2$$$ является гамильтоновым.

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

Рассмотрим запросы:

  • Вершина $$$1$$$ имеет степень хотя бы $$$3$$$, но при этом она соединена со всеми вершинами, поэтому сообщается «$$$1\ 0$$$». После этого вершина $$$1$$$ удаляется из графа.
  • Оставшиеся вершины $$$2$$$, $$$3$$$ и $$$4$$$ имеют степень хотя бы $$$0$$$, но из них вершина $$$4$$$ имеет минимальную степень $$$0$$$ (вершины $$$2$$$ и $$$3$$$ имеют степень $$$1$$$). Вершина $$$4$$$ не соединена с обеими вершинами $$$2$$$ и $$$3$$$, поэтому сообщается вершина $$$2$$$ (так как она имеет минимальный номер). После этого вершина $$$4$$$ удаляется из графа.

Путь $$$4 - 1 - 2 - 3$$$ является гамильтоновым.

В третьем наборе входных данных граф состоит из $$$2$$$ вершин, соединённых ребром.