E2. Поймай крота (сложная версия)
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

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

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

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

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

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

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

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

Первая строка каждого набора входных данных содержит одно целое число $$$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$$$.

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

Пример
Входные данные
2
2
1 2

1

6
1 2
1 3
1 4
4 5
5 6

0

0

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



? 2

! 2






? 2

? 6

? 4

! 4
Примечание

В первом наборе входных данных крот изначально находится в вершине $$$2$$$.

Для запроса «? 2», жюри возвращает $$$1$$$, потому что крот находится в поддереве вершины $$$2$$$. После этого запроса крот не перемещается.

Ответ $$$2$$$ — это текущая вершина, где находится крот, поэтому ответ считается правильным.

Во втором наборе входных данных крот изначально находится в вершине $$$6$$$.

Для запроса «? 2», жюри возвращает $$$0$$$, потому что крот не находится в поддереве вершины $$$2$$$. После этого запроса крот перемещается из вершины $$$6$$$ в вершину $$$5$$$.

Для запроса «? 6», жюри возвращает $$$0$$$, потому что крот не находится в поддереве вершины $$$6$$$. После этого запроса крот перемещается из вершины $$$5$$$ в вершину $$$4$$$.

Для запроса «? 4», жюри возвращает $$$1$$$, потому что крот находится в поддереве вершины $$$4$$$. После этого запроса крот не перемещается.

Ответ $$$4$$$ — это текущая вершина, где находится крот, поэтому ответ считается правильным.

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