Олимпиадный тренинг

Задача . D. Потерянное дерево

Задача

Темы: Деревья интерактив Конструктив *1800

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

Маленький Дорми на фестивале столкнулся со странной головоломкой: ему нужно угадать ребра невзвешенного дерева из $n$ вершин! Вершины дерева пронумерованы от $1$ до $n$.

Ему разрешается задавать организатору вопросы одного вида:

Маленький Дорми выбирает вершину $r$ ($1 \le r \le n$), а организатор в ответ предоставляет ему массив целых чисел $d_1, d_2, \ldots, d_n$, где $d_i$ — длина кратчайшего пути из $r$ в вершину $i$ для всех $1 \le i \le n$.

Кроме того, чтобы сделать головоломку нечестной дополнительно озадачить Дорми, организатор разрешает задать не более $\lceil\frac{n}{2}\rceil$ вопросов, где $\lceil x \rceil$ обозначает наименьшее целое число, большее либо равное $x$.

Маленький Дорми переживает, что может не угадать дерево, поэтому ему нужна ваша помощь!

Обратите внимание, что организатор создает дерево до начала взаимодействия, и не меняет его в процессе взаимодействия.

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

Первая строка содержит одно целое число $n$ ($2 \le n \le 2\,000$) — количество вершин в дереве.

После этого начинается взаимодействие.

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

Когда ваша программа нашла дерево, выведите одну строку, содержащую «!», а затем $n-1$ строку, каждая из которых содержит два целых числа $a$ и $b$, означающие ребро, соединяющее вершины $a$ и $b$ ($1 \le a, b \le n$). После этого ваша программа должна сбросить буфер вывода и завершиться.

Вы можете выводить ребра дерева в любом порядке, ребро $(a,b)$ и ребро $(b,a)$ считаются одним и тем же ребром. Вывод ответа не считается как один из вопросов.

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

После чтения количества вершин, вы можете задать не более $\lceil\frac{n}{2}\rceil$ вопросов. Каждый вопрос задается в формате «? r», где целое число $r$ ($1 \le r \le n$) обозначает номер вершины, которую вы выбрали для этого вопроса.

После этого считайте $n$ целых чисел $d_1, d_2, \ldots, d_n$ в отдельной строке, где $d_i$ равно длине кратчайшего пути из вершины $r$ в вершину $i$.

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

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

Если в какой-то момент вы задали больше, чем $\lceil \frac{n}{2} \rceil$ вопросов, взаимодействие прекратится, и вы получите вердикт «Неправильный ответ».

Взломы

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

Первая строка содержит целое число $n$ ($2 \le n \le 2\,000$).

Следующие $n−1$ строк содержат два целых числа $u$ и $v$ ($1 \le u,v \le n$), обозначающие ребро между вершинами $u$ и $v$ ($u \neq v$). Эти $n-1$ ребер должны образовывать дерево.

Примечание

Ниже показано дерево из первого примера.