Это сложная версия задачи. Единственное отличие — это ограничение на количество запросов.

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

Вам дано дерево из $$$n$$$ вершин с вершиной $$$1$$$ в качестве корневой.

В одной из вершин спрятан крот. Чтобы найти его положение, вы можете выбрать вершину $$$x$$$ ($$$1 \le x \le n$$$) и сделать запрос к жюри. После этого жюри вернет $$$1$$$, если крот находится в поддереве вершины $$$x$$$. В противном случае жюри вернет $$$0$$$. Если жюри возвращает $$$0$$$ и крот не находится в корневой вершине $$$1$$$, крот переместится в вершину-родителя той вершины, в которой он находится в данный момент.

Используя не более $$$160$$$ операций, найдите текущую вершину, в которой находится крот.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$2 \le n \le 5000$$$).

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

Гарантируется, что входные данные представляют собой дерево.

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

Чтобы сделать запрос, вам нужно выбрать вершину $$$x$$$ ($$$1 \le x \le n$$$) и вывести строку следующего вида:

• «? x»

После этого вы получите:

• $$$0$$$, если крот не находится в поддереве $$$x$$$;
• $$$1$$$, если крот находится в поддереве $$$x$$$.

Вы можете сделать не более $$$160$$$ запросов такого вида для каждого набора входных данных.

Затем, если вы определили текущую вершину, где находится крот, выведите строку следующего вида:

• «! x»

Обратите внимание, что эта строка не считается запросом и не учитывается при подсчете количества заданных запросов.

После этого переходите к следующему набору входных данных.

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

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

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

Взломы

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

Первая строка содержит количество наборов входных данных $$$t$$$ ($$$1 \le t \le 100$$$). Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$x$$$ ($$$2 \le n \le 5000$$$, $$$1 \le x \le n$$$), описывающие размер дерева и начальное положение крота.

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

Входные данные обязаны представлять собой дерево.