| Codeforces Round 951 (Div. 2) |
|---|
| Закончено |
Это интерактивная задача.
Костяныч загадал полный неориентированный граф$$$^{\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$$$ вершин, соединённых ребром.
