CF1305D.Kuroni and the Celebration

This is an interactive problem.

After getting AC after 13 Time Limit Exceeded verdicts on a geometry problem, Kuroni went to an Italian restaurant to celebrate this holy achievement. Unfortunately, the excess sauce disoriented him, and he's now lost!

The United States of America can be modeled as a tree (why though) with $n$ vertices. The tree is rooted at vertex $r$, wherein lies Kuroni's hotel.

Kuroni has a phone app designed to help him in such emergency cases. To use the app, he has to input two vertices $u$ and $v$, and it'll return a vertex $w$, which is the lowest common ancestor of those two vertices.

However, since the phone's battery has been almost drained out from live-streaming Kuroni's celebration party, he could only use the app at most $\lfloor \frac{n}{2} \rfloor$ times. After that, the phone would die and there will be nothing left to help our dear friend! :(

As the night is cold and dark, Kuroni needs to get back, so that he can reunite with his comfy bed and pillow(s). Can you help him figure out his hotel's location?

Interaction

The interaction starts with reading a single integer $n$ ($2 \le n \le 1000$), the number of vertices of the tree.

Then you will read $n-1$ lines, the $i$-th of them has two integers $x_i$ and $y_i$ ($1 \le x_i, y_i \le n$, $x_i \ne y_i$), denoting there is an edge connecting vertices $x_i$ and $y_i$. It is guaranteed that the edges will form a tree.

Then you can make queries of type "? u v" ($1 \le u, v \le n$) to find the lowest common ancestor of vertex $u$ and $v$.

After the query, read the result $w$ as an integer.

In case your query is invalid or you asked more than $\lfloor \frac{n}{2} \rfloor$ queries, the program will print $-1$ and will finish interaction. You will receive a Wrong answer verdict. Make sure to exit immediately to avoid getting other verdicts.

When you find out the vertex $r$, print "! $r$" and quit after that. This query does not count towards the $\lfloor \frac{n}{2} \rfloor$ limit.

Note that the tree is fixed beforehand and will not change during the queries, i.e. the interactor is not adaptive.

After printing any query do not forget to print end of line and flush the output. Otherwise, you might get Idleness limit exceeded. To do this, use:

• fflush(stdout) or cout.flush() in C++;
• System.out.flush() in Java;
• flush(output) in Pascal;
• stdout.flush() in Python;
• see the documentation for other languages.

Hacks

To hack, use the following format:

The first line should contain two integers $n$ and $r$ ($2 \le n \le 1000$, $1 \le r \le n$), denoting the number of vertices and the vertex with Kuroni's hotel.

The $i$-th of the next $n-1$ lines should contain two integers $x_i$ and $y_i$ ($1 \le x_i, y_i \le n$) — denoting there is an edge connecting vertex $x_i$ and $y_i$.

The edges presented should form a tree.

这是一个交互式问题。

在一道几何题上经历了 13 次“时间超限（Time Limit Exceeded）”判决后终于获得 AC，Kuroni 前往一家意大利餐厅庆祝这一神圣成就。不幸的是，过多的酱汁使他晕头转向，如今迷路了！

美国合众国可被建模为一棵含 $n$ 个顶点的树（虽然原因不明），该树以顶点 $r$ 为根，而 Kuroni 的酒店就位于该顶点。

Kuroni 有一款专为此类紧急情况设计的手机应用程序。要使用该程序，他需输入两个顶点 $u$ 和 $v$，程序将返回一个顶点 $w$，即这两个顶点的最近公共祖先（lowest common ancestor）。

然而，由于手机电池在直播 Kuroni 庆祝派对的过程中几乎耗尽，他最多只能使用该程序 $\lfloor \frac{n}{2} \rfloor$ 次。此后手机将彻底关机，再无任何工具能帮助我们亲爱的友人！:(

夜寒且黑，Kuroni 急需返程，以便与他舒适的床铺和枕头重聚。你能帮他确定酒店所在的位置吗？

交互流程

交互开始时，首先读入一个整数 $n$（$2 \le n \le 1000$），表示树的顶点数。

接着读入 $n-1$ 行，其中第 $i$ 行包含两个整数 $x_i$ 和 $y_i$（$1 \le x_i, y_i \le n$，且 $x_i \ne y_i$），表示顶点 $x_i$ 与 $y_i$ 之间存在一条边。保证所给边构成一棵树。

随后，你可以发出形如 ? u v（$1 \le u, v \le n$）的查询，以获取顶点 $u$ 与 $v$ 的最近公共祖先。

每次查询后，请读入一个整数结果 $w$。

若你的查询非法，或查询次数超过 $\lfloor \frac{n}{2} \rfloor$ 次，则程序将输出 $-1$ 并终止交互。此时你将收到“答案错误（Wrong answer）”判决。请务必立即退出程序，以免引发其他判决。

当你确定顶点 $r$ 后，请输出 ! $r$ 并立即退出。该输出不计入 $\lfloor \frac{n}{2} \rfloor$ 次查询限制。

注意：该树在交互开始前即已固定，且在整个查询过程中不会改变，即交互器是非自适应的（not adaptive）。

每次输出任意查询后，切勿忘记输出换行符并刷新输出缓冲区。否则你可能会收到“空闲超时（Idleness limit exceeded）”判决。为此，请使用以下方式：

• C++ 中使用 fflush(stdout) 或 cout.flush()；
• Java 中使用 System.out.flush()；
• Pascal 中使用 flush(output)；
• Python 中使用 stdout.flush()；
• 其他语言请参阅相应文档。

Hack 方法

进行 Hack 时，请采用如下格式：

第一行应包含两个整数 $n$ 和 $r$（$2 \le n \le 1000$，$1 \le r \le n$），分别表示顶点数及 Kuroni 酒店所在的顶点。

接下来的 $n-1$ 行中，第 $i$ 行应包含两个整数 $x_i$ 和 $y_i$（$1 \le x_i, y_i \le n$），表示顶点 $x_i$ 与 $y_i$ 之间存在一条边。

所给出的边必须构成一棵树。

Note that the example interaction contains extra empty lines so that it's easier to read. The real interaction doesn't contain any empty lines and you shouldn't print any extra empty lines as well.

The image below demonstrates the tree in the sample test:

注意：示例交互中包含额外的空行，以便于阅读。实际交互中不包含任何空行，因此你也不应输出任何额外的空行。

下图展示了样例测试中的树：