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

Так как маленький Эрики прошел на Международную олимпиаду школьников по информатике в этом году, он получил подарок от своих друзей: дерево с $$$n$$$ вершинами!

По пути к месту проведения Эрики было скучно, поэтому он решил сыграть в игру с маленьким Ивонном с использованием нового дерева. Сначала Ивонн загадывает две (не обязательно различные) вершины $$$a$$$ и $$$b$$$ в этом дереве (не сообщая их Эрики), а затем сообщает ему подсказку $$$f$$$ — одну из вершин на простом пути от $$$a$$$ до $$$b$$$.

Затем маленький Эрики может спрашивать следующие вопросы:

• Если подвесить дерево за вершину $$$r$$$ (Эрики может выбрать $$$r$$$), какая вершина будет наименьшим общим предком вершин $$$a$$$ и $$$b$$$?

Задача маленького Эрики — найти вершины $$$a$$$ и $$$b$$$.

Маленький Ивонн считает игру слишком простой, поэтому в начале игры, перед тем, как дать подсказку $$$f$$$, он просит Эрики найти максимальное количество запросов, необходимых для нахождения $$$a$$$ и $$$b$$$ для всех возможных значений $$$a$$$, $$$b$$$ и $$$f$$$ в предположении, что Эрики действует оптимально. Под оптимальными действиями подразумевается стратегия, делающая наименьшее число запросов. Конечно, после того, как маленький Эрики скажет это максимальное количество запросов, Ивонн не разрешит сделать больше запросов в самой игре.

Дерево, $$$a$$$, $$$b$$$ и $$$f$$$ фиксированы до начала игры и не меняются в зависимости от запросов.

Сначала считайте строку, содержащую одно целое число $$$n$$$ ($$$1 \le n \le 10^5$$$) — количество вершин в дереве.

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

После этого вы должны вывести $$$k$$$ — максимальное число запросов, необходимое для определения $$$a$$$ и $$$b$$$ по всем возможным значениям $$$a$$$, $$$b$$$ и $$$f$$$ в предположении оптимальной игры. Вы должны вывести перевод строки и сбросить буфер вывода после вывода $$$k$$$.

Затем считайте одно целое число $$$f$$$ ($$$1 \le f \le n$$$) — подсказку: вершину на пути от $$$a$$$ до $$$b$$$ включительно.

После этого вы можете делать запросы. Вам будет разрешено сделать не более $$$k$$$ запросов, где $$$k$$$ — число, которое вы вывели.

Для того, чтобы сделать запрос, выведите «? r», где $$$r$$$ — целое число, $$$1 \le r \le n$$$, обозначающее, за какую вершину вы хотите подвесить дерево.

В ответ вы получите целое число $$$x$$$ ($$$1 \le x \le n$$$) — наименьший общий предок вершин $$$a$$$ и $$$b$$$, если дерево подвесить за $$$r$$$.

Когда ваша программа определит $$$a$$$ и $$$b$$$, выведите их в следующем формате: «! a b», где $$$a$$$ и $$$b$$$ — две загаданные вершины, и завершите программу сразу после сброса буфера вывода. Вы можете вывести $$$a$$$ и $$$b$$$ в любом порядке.

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

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

Если вы сделаете некорректный вывод, или сделаете более $$$k$$$ запросов, взаимодействие прекратится и вы получите вердикт «Неправильный ответ». Вывод считается некорректным, если это некорректный запрос, или вы вывели $$$k$$$, меньшее $$$0$$$ или большее $$$n$$$.

Взломы

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

Первая строка содержит одно целое число $$$n$$$ ($$$1 \le n \le 10^5$$$).

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

Следующая строка содержит два целых числа $$$a$$$ и $$$b$$$ ($$$1 \le a,b \le n$$$).

Последняя строка должна содержать одно целое число $$$f$$$ ($$$1 \le f \le n$$$). Вершина $$$f$$$ должна лежать на простом пути от $$$a$$$ до $$$b$$$ включительно.