G. Paths in a Tree
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

This is an interactive problem.

In this interactive problem, you are given an acyclic, connected, undirected graph consisting of $$$n$$$ vertices. We define a path between two vertices $$$v$$$ and $$$u$$$ as a sequence of distinct vertices $$$p_1, p_2,\dots p_k$$$ such that $$$p_1 = v$$$, $$$p_k = u$$$, and for all $$$i$$$ ($$$1 \le i \lt k$$$), there exists an edge between vertices $$$p_i$$$ and $$$p_{i+1}$$$.

There are hidden vertices $$$x$$$ and $$$y$$$ (they may coincide). You can make the following queries:

  • Choose two vertices $$$a$$$, $$$b$$$ ($$$1\le a, b\le n$$$). The jury will respond with $$$1$$$ if the path between vertices $$$x$$$, $$$y$$$ and the path between vertices $$$a$$$, $$$b$$$ share at least one common vertex, and will respond with $$$0$$$ otherwise.
Your task is to find at least one vertex on the path between $$$x$$$ and $$$y$$$ in no more than $$$\lfloor\frac{n}{2}\rfloor + 1$$$ queries.

Note that the interactor is adaptive, which means that the hidden vertices may change depending on your queries, but will not contradict previous queries.

Input

Each test consists of several test cases. The first line contains one integer $$$t$$$ ($$$1\le t\le 10^4$$$) — the number of test cases. The following lines describe the test cases.

The first line of each test case contains one integer $$$n$$$ ($$$2\le n\le 2\cdot 10^5$$$) — the number of vertices in the graph.

Next, there are $$$n - 1$$$ lines, each containing two integers $$$v$$$, $$$u$$$ ($$$1\le v, u\le n$$$), indicating that vertices $$$v$$$ and $$$u$$$ are connected by an edge in the graph.

It is guaranteed that the sum of $$$n$$$ across all test cases does not exceed $$$2\cdot 10^5$$$.

Interaction

To find any vertex on the path, you can use no more than $$$\lfloor\frac{n}{2}\rfloor + 1$$$ queries. For this, use queries of the form "? $$$a$$$ $$$b$$$".

After each query, read one number, either $$$0$$$ or $$$1$$$ — the response to the query.

When you find one of the required vertices, output one line in the following format: "! $$$v$$$" ($$$1\le v\le n$$$), where $$$v$$$ is the vertex you found.

If your program makes more than $$$\lfloor\frac{n}{2}\rfloor + 1$$$ queries for one test case, the response to the query will be $$$-1$$$, and after receiving such a response, your program should terminate immediately to receive a verdict of Incorrect answer. Otherwise, it may receive any other verdict.

After outputting a query, do not forget to output a newline and flush the output buffer. Otherwise, you will receive a verdict of Solution "timed out". To flush the buffer, use:

  • $$$\tt{fflush(stdout)}$$$ or $$$\tt{cout.flush()}$$$ in C++;
  • $$$\tt{System.out.flush()}$$$ in Java;
  • $$$\tt{flush(output)}$$$ in Pascal;
  • $$$\tt{stdout.flush()}$$$ in Python;
  • refer to the documentation for other languages.
Example
Input
3

2
1 2

1


3
1 2
1 3

0

0


4
1 2
2 3
2 4

0

1
Output
? 1 1

! 1


? 1 1

? 2 2

! 3


? 1 3

? 4 4

! 4