CF1174F.Ehab and the Big Finale

This is an interactive problem.

You're given a tree consisting of $n$ nodes, rooted at node $1$. A tree is a connected graph with no cycles.

We chose a hidden node $x$. In order to find this node, you can ask queries of two types:

• d $u$ ($1 \le u \le n$). We will answer with the distance between nodes $u$ and $x$. The distance between two nodes is the number of edges in the shortest path between them.
• s $u$ ($1 \le u \le n$). We will answer with the second node on the path from $u$ to $x$. However, there's a plot twist. If $u$ is not an ancestor of $x$, you'll receive "Wrong answer" verdict!

Node $a$ is called an ancestor of node $b$ if $a \ne b$ and the shortest path from node $1$ to node $b$ passes through node $a$. Note that in this problem a node is not an ancestor of itself.

Can you find $x$ in no more than $36$ queries? The hidden node is fixed in each test beforehand and does not depend on your queries.

这是一个交互式问题。

你将得到一棵包含 $n$ 个节点的树，根节点为节点 $1$。树是一种无环的连通图。

我们选定一个隐藏节点 $x$。为了找出该节点，你可以提出两类查询：

• d u（其中 $1 \le u \le n$）：我们将返回节点 $u$ 与节点 $x$ 之间的距离。两个节点间的距离定义为它们之间最短路径所含边的数量。
• s u（其中 $1 \le u \le n$）：我们将返回从节点 $u$ 到节点 $x$ 的路径上的第二个节点。但这里有一个转折：若 $u$ 不是 $x$ 的祖先，则你会收到 “Wrong answer”（答案错误）判据！

节点 $a$ 被称为节点 $b$ 的祖先，当且仅当 $a \ne b$，且从根节点 $1$ 到节点 $b$ 的最短路径经过节点 $a$。注意，在本题中，一个节点不被视为自身的祖先。

你能否在不超过 $36$ 次查询内确定 $x$？在每个测试用例中，隐藏节点 $x$ 在开始时即已固定，且不随你的查询而改变。

The first line contains the integer $n$ ($2 \le n \le 2 \cdot 10^5$) — the number of nodes in the tree.

Each of the next $n-1$ lines contains two space-separated integers $u$ and $v$ ($1 \le u,v \le n$) that mean there's an edge between nodes $u$ and $v$. It's guaranteed that the given graph is a tree.

第一行包含一个整数 $n$（$2 \le n \le 2 \cdot 10^5$）——树中节点的数量。

接下来的 $n-1$ 行每行包含两个用空格分隔的整数 $u$ 和 $v$（$1 \le u,v \le n$），表示节点 $u$ 与节点 $v$ 之间存在一条边。保证所给图是一棵树。

To print the answer, print "! x" (without quotes).

要输出答案，请输出“! x”（不含引号）。

In the first example, the hidden node is node $5$.

We first ask about the distance between node $x$ and node $2$. The answer is $3$, so node $x$ is either $4$ or $5$. We then ask about the second node in the path from node $3$ to node $x$. Note here that node $3$ is an ancestor of node $5$. We receive node $5$ as the answer. Finally, we report that the hidden node is node $5$.

在第一个例子中，隐藏节点是节点 $5$。

我们首先询问节点 $x$ 与节点 $2$ 之间的距离。回答为 $3$，因此节点 $x$ 要么是 $4$，要么是 $5$。接着，我们询问从节点 $3$ 到节点 $x$ 的路径上的第二个节点。注意，此处节点 $3$ 是节点 $5$ 的祖先。我们得到的回答是节点 $5$。最后，我们报告隐藏节点为节点 $5$。