Это интерактивная задача.
Костяныч загадал полный неориентированный граф\(^{\dagger}\) на \(n\) вершинах, после чего удалил из него ровно \((n - 2)\) ребра. Вы можете делать запросы следующего вида:
- «? \(d\)» — Костяныч сообщает вам номер вершины \(v\) со степенью хотя бы \(d\). Из всех возможных таких вершин он выбирает вершину с минимальной степенью, если таких несколько, то с минимальным номером. Также он сообщает вам номер другой вершины из графа, с которой \(v\) не соединена ребром (если такой не нашлось, то сообщается \(0\)). Из всех возможных таких вершин он выбирает вершину с минимальным номером. Затем он удаляет вершину \(v\) и все выходящие из неё рёбра. Если требуемой вершины \(v\) не нашлось, то сообщается «\(0\ 0\)».
Найдите в исходном графе гамильтонов путь\(^{\ddagger}\) за не более чем \(n\) запросов. Можно показать, что при данных ограничениях гамильтонов путь всегда существует.
\(^{\dagger}\)Полным неориентированным графом называется граф, в котором между любой парой различных вершин есть ровно одно неориентированное ребро. Таким образом, полный неориентированный граф на \(n\) вершинах содержит \(\frac{n(n-1)}{2}\) рёбер.
\(^{\ddagger}\)Гамильтоновым путём в графе называется путь, который проходит через каждую вершину ровно один раз.
Протокол взаимодействия
Взаимодействие для каждого набора входных данных начинается с чтения целого числа \(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\) в графе нет, поэтому сообщается «\(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\) вершин, соединённых ребром.