Задача . G. Угадайте центроид

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

Есть загаданное дерево, состоящее из \(n\) вершин, которое имеет только один центроид. Сначала вам известно только \(n\), и ваша задача  — найти центроид дерева.

Вы можете спросить расстояние между любыми двумя вершинами не более \(2\cdot10^5\) раз.

Обратите внимание, что интерактор является неадаптивным. То есть, дерево фиксировано в каждом тесте заранее и не зависит от ваших запросов.

Вершина называется центроидом, если ее удаление разбивает дерево на поддеревья, в каждом из которых не более \(\lfloor\frac{n}{2}\rfloor\) вершин.

Начните взаимодействие с чтения \(n\).

Чтобы задать запрос о расстоянии между двумя вершинами \(u, v\) (\(1 \le u, v \le n\)), выведите «? u v».

Если вы определили, что центроидом дерева является \(x\), используйте «! x» для вывода ответа.

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

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

В этой задаче взломы отключены.

Гарантируется, что в этой задаче есть не более \(500\) тестов.