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

Мизуки выбрала секретное дерево с $$$n$$$ вершинами, пронумерованными от $$$1$$$ до $$$n$$$, и попросила вас отгадать его с помощью запросов следующего типа:

• «? a b» — Мизуки скажет вам, какая вершина $$$x$$$ минимизирует $$$|d(a,x) - d(b,x)|$$$, где $$$d(x,y)$$$ — расстояние между вершинами $$$x$$$ и $$$y$$$. Если таких вершин несколько, Мизуки укажет вам ту, которая минимизирует $$$d(a,x)$$$.

Выясните структуру секретного дерева Мизуки, используя не более $$$15n$$$ запросов!

Взаимодействие начинается с чтения целого числа $$$n$$$.

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

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

Чтобы сообщить ответ, выведите строку в формате «! $$$a_1$$$ $$$b_1$$$ $$$a_2$$$ $$$b_2$$$ ... $$$a_{n-1}$$$ $$$b_{n-1}$$$» (без кавычек), что означает, что между вершинами $$$a_i$$$ и $$$b_i$$$ существует ребро для каждого $$$1 \le i \le n-1$$$. Вы можете выводить ребра в любом порядке.

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

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

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

Взломы

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

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

Затем следует $$$n-1$$$ строка. В $$$i$$$-й из них содержатся два целых числа $$$a_i$$$ и $$$b_i$$$ ($$$1 \le a_i, b_i \le n$$$), что означает, что между $$$a_i$$$ и $$$b_i$$$ в скрытом дереве есть ребро.

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