Это интерактивная задача.
Мизуки выбрала секретное дерево с \(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\).
Примечание
Дерево — это связный неориентированный граф без циклов. Дерево с \(n\) вершинами всегда будет иметь \(n-1\) ребро.
В примере ответ на «? 1 2» равен \(1\). Это означает, что между вершинами \(1\) и \(2\) есть ребро.
Ответ на запрос «? 1 3» равен \(1\). Это означает, что между вершинами \(1\) и \(3\) есть ребро.
Ответ на запрос «? 1 4» равен \(3\). Можно доказать, что это возможно только в том случае, если вершина \(3\) соединена с вершинами \(1\) и \(4\).
Следовательно, ребра дерева — это \((1,2)\), \((1,3)\) и \((3,4)\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
1
4
1
1
3
|
? 1 2
? 1 3
? 1 4
! 1 2 1 3 3 4
|