E. Найти вершину
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

Вам задано дерево — связный неориентированный граф без циклов. В нём загадали одну из вершин. Вы можете задавать вопросы интерактору: за один вопрос вы можете выбрать ребро и узнать, какой из двух концов ребра находится ближе к загаданной вершине, то есть, до какого из двух концов меньше кратчайшее расстояние от загаданной вершины. Вам требуется определить загаданную вершину за минимальное для данного дерева число запросов в худшем случае.

Обратите внимание, что загаданная вершина может быть не фиксирована интерактором заранее: в зависимости от ваших запросов он может менять её на любую другую, с условием, что это не противоречит ответам на предыдущие запросы.

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

В первой строке входных данных содержится целое число $$$n$$$ ($$$2 \le n \le 100$$$) — количество вершин в дереве.

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

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

После считывания выходных данных вы можете отправлять интерактору запросы двух типов:

  1. «? $$$u$$$ $$$v$$$» — узнать для ребра дерева $$$(u, v)$$$ ($$$1 \le u, v \le n$$$), какой из его концов ближе к загаданной вершине. В ответ вы получите одно число: номер одной из двух вершин. Обратите внимание, что $$$u$$$ и $$$v$$$ должны быть соединены ребром в дереве, поэтому они не могут находиться на равном расстоянии от загаданной вершины.
  2. «! $$$u$$$» — сообщить интерактору о том, что вы выяснили номер загаданной вершины. После вывода этой команды ваша программа должна немедленно завершиться.

После каждого вопроса не забудьте вывести перевод строки и сбросить буфер вывода. В противном случае вы получите вердикт Idleness Limit Exceeded или Превышено реальное время работы. Для сброса буфера вы можете использовать:

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

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

Примеры
Входные данные
5
1 2
2 3
3 4
4 5
3
2
1
Выходные данные
? 3 4
? 2 3
? 1 2
! 1
Входные данные
5
2 1
3 1
4 1
5 1
1
1
4
Выходные данные
? 1 2
? 1 3
? 1 4
! 4
Примечание

Взломы в данной задаче запрещены.