E. Угадывание дерева
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Maozon - Stasis

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

Интерактор хранит скрытое дерево из $$$n$$$ вершин, пронумерованных от $$$1$$$ до $$$n$$$. Ваша задача — найти это дерево, используя не более $$$2n - 2$$$ запросов.

В каждом запросе вы выбираете вершину $$$x$$$ и перестановку $$$p_1, p_2, \ldots, p_n$$$ целых чисел от $$$1$$$ до $$$n$$$, а интерактор возвращает $$$$$$\sum_{i = 1}^{n} \max_{j \in \text{path}(i, x)} p_j,$$$$$$ где $$$\text{path}(i, x)$$$ — множество вершин на простом пути между $$$i$$$ и $$$x$$$, включая обе вершины $$$i$$$ и $$$x$$$ (в частности, $$$\text{path}(x, x) = \{x\}$$$).

Иными словами, для каждой вершины $$$i$$$ рассмотрите все вершины $$$j$$$ на единственном пути от $$$i$$$ до $$$x$$$, включая оба конца пути, и возьмите наибольшее значение $$$p_j$$$ среди них. Интерактор возвращает сумму этих максимальных значений по всем $$$n$$$ вершинам $$$i$$$.

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

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

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

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

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

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

Когда вы найдёте дерево, выведите строку, содержащую «!», а затем $$$n - 1$$$ строк, каждая из которых содержит два целых числа $$$u$$$ и $$$v$$$, означающих, что между вершинами $$$u$$$ и $$$v$$$ есть ребро. Рёбра можно выводить в любом порядке. Вывод ответа не считается запросом. После вывода всех рёбер дерева сбросьте буфер вывода. После этого перейдите к следующему набору входных данных или завершите программу, если это был последний набор.

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

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

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

Взломы

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

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

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

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

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

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

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

3

6

7

4

10

13

4

10

11

13

16

8

10
Выходные данные
!
1 2

? 1 1 2 3

? 2 1 2 3

!
3 1
1 2

? 1 1 2 3 4

? 2 1 3 4 2

!
1 2
1 3
2 4

? 1 1 2 3 4

? 1 2 1 3 4

? 1 3 1 2 4

? 1 4 1 2 3

!
1 2
1 3
1 4

!
1 2
2 3
3 4
4 5
5 6
6 7
7 8

!
1 2
1 3
2 4
2 5
3 6
3 7
4 8
5 9
6 10
Примечание

В первом наборе входных данных единственное возможное дерево на двух вершинах состоит из одного ребра $$$(1, 2)$$$, поэтому запросы не требуются. Ответ — !, после которого выводится это ребро.

Во втором наборе входных данных дерево содержит два ребра: $$$(1, 2)$$$ и $$$(1, 3)$$$.

В первом запросе $$$x = 1$$$ и $$$p = [1, 2, 3]$$$, поэтому интерактор возвращает $$$\max\{1\} + \max\{2, 1\} + \max\{3, 1\} = 6$$$.

Во втором запросе $$$x = 2$$$ и $$$p = [1, 2, 3]$$$, поэтому интерактор возвращает $$$\max\{1, 2\} + \max\{2\} + \max\{3, 1, 2\} = 7$$$.