CF1534H.Lost Nodes

This is an interactive problem.

As he qualified for IOI this year, Little Ericyi was given a gift from all his friends: a tree of $n$ nodes!

On the flight to IOI Little Ericyi was very bored, so he decided to play a game with Little Yvonne with his new tree. First, Little Yvonne selects two (not necessarily different) nodes $a$ and $b$ on the tree (without telling Ericyi), and then gives him a hint $f$ (which is some node on the path from $a$ to $b$).

Then, Little Ericyi is able to ask the following question repeatedly:

• If I rooted the tree at node $r$ (Ericyi gets to choose $r$), what would be the Lowest Common Ancestor of $a$ and $b$?

Little Ericyi's goal is to find the nodes $a$ and $b$, and report them to Little Yvonne.

However, Little Yvonne thought this game was too easy, so before he gives the hint $f$ to Little Ericyi, he also wants him to first find the maximum number of queries required to determine $a$ and $b$ over all possibilities of $a$, $b$, and $f$ assuming Little Ericyi plays optimally. Little Ericyi defines an optimal strategy as one that makes the minimum number of queries. Of course, once Little Ericyi replies with the maximum number of queries, Little Yvonne will only let him use that many queries in the game.

The tree, $a$, $b$, and $f$ are all fixed before the start of the game and do not change as queries are made.

Interaction

First read a line containing the integer $n$ ($1 \le n \le 10^5$), the number of nodes in the tree.

The next $n−1$ lines describe Little Ericyi's tree. These lines contain two integers $u$ and $v$ ($1 \le u,v \le n$) denoting an edge between $u$ and $v$ ($u \neq v$). It is guaranteed that these edges form a tree.

After that you should output $k$, the maximum number of queries needed to determine $a$ and $b$ over all possibilities of $a$, $b$, and $f$ assuming Little Ericyi plays optimally. You should output end of line and flush the output after printing $k$.

After that read a line containing the integer $f$ ($1 \le f \le n$) — the hint: a node on the path from $a$ to $b$, inclusive.

After that, you can start making queries. You will be limited to making at most $k$ queries, where $k$ is the number you printed.

Each query is made in the format "? r", where $r$ is an integer $1 \le r \le n$ denoting the root node you want for the query.

You will then receive an integer $x$ ($1 \le x \le n$), the Lowest Common Ancestor of $a$ and $b$ if the tree was rooted at $r$.

When your program has found the nodes $a$, $b$, report the answer in the following format: "! a b", where $a$ and $b$ are the two hidden nodes and terminate your program normally immediately after flushing the output stream. You may output $a$ and $b$ in any order.

After printing a query do not forget to output end of line and flush the output. Otherwise, you will 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 documentation for other languages.

If at any point you make an invalid output or make more than $k$ queries, the interaction will terminate and you will receive a Wrong Answer verdict. An invalid output is defined as either an invalid query or a value of $k$ less than $0$ or greater than $n$.

Hacks

To hack a solution, use the following format:

The first line contains the integer $n$ ($1 \le n \le 10^5$).

The next $n−1$ lines contain two integers $u$ and $v$ ($1 \le u,v \le n$) denoting an edge between $u$ and $v$ ($u \neq v$). These $n-1$ edges must form a tree.

The next line of input contains the nodes $a$ and $b$ ($1 \le a,b \le n$), separated by a space.

The final line of input contains the integer $f$ ($1 \le f \le n$). Node $f$ should be on the simple path from $a$ to $b$ (inclusive).

这是一个交互式问题。

由于今年成功入选国际信息学奥林匹克竞赛（IOI），小 Ericyi 收到了朋友们送的一份礼物：一棵包含 $n$ 个节点的树！

在飞往 IOI 的航班上，小 Ericyi 感到非常无聊，于是决定和小 Yvonne 用这棵新树玩一个游戏。首先，小 Yvonne 在树上选定两个（不一定不同）的节点 $a$ 和 $b$（但不告诉 Ericyi），然后给她一个提示 $f$（即 $a$ 到 $b$ 路径上的某个节点）。

接着，小 Ericyi 可以反复提出如下询问：

• 若将树以节点 $r$ 为根（Ericyi 自行选择 $r$），那么 $a$ 和 $b$ 的最近公共祖先（LCA）是什么？

小 Ericyi 的目标是找出节点 $a$ 和 $b$，并将其报告给小 Yvonne。

然而，小 Yvonne 认为这个游戏太简单了，因此在将提示 $f$ 告诉小 Ericyi 之前，她还要求他先计算出：在所有可能的 $a$、$b$ 和 $f$ 组合下，假设小 Ericyi 采用最优策略，确定 $a$ 和 $b$ 所需的最大查询次数。小 Ericyi 将“最优策略”定义为使查询次数最少的策略。当然，一旦小 Ericyi 报出该最大查询次数 $k$，小 Yvonne 就只允许他在游戏中使用至多 $k$ 次查询。

整棵树、隐藏的 $a$、$b$ 和 $f$ 都在游戏开始前就已固定，并且在后续查询过程中不会改变。

交互流程

首先读入一行，包含整数 $n$（$1 \le n \le 10^5$），表示树的节点数。

接下来 $n-1$ 行描述小 Ericyi 的树。每行包含两个整数 $u$ 和 $v$（$1 \le u,v \le n$），表示 $u$ 与 $v$ 之间存在一条边（$u \neq v$）。保证这些边构成一棵树。

之后，你需要输出一个整数 $k$，即在所有可能的 $a$、$b$ 和 $f$ 组合下，假设小 Ericyi 采用最优策略，确定 $a$ 和 $b$ 所需的最大查询次数。输出 $k$ 后，请换行并刷新输出流。

随后读入一行，包含整数 $f$（$1 \le f \le n$）——这是提示：$a$ 到 $b$ 路径上的一个节点（端点也包含在内）。

此后，你就可以开始进行查询。你最多只能进行 $k$ 次查询，其中 $k$ 即为你之前输出的数值。

每次查询格式为 "? r"，其中 $r$ 是一个整数（$1 \le r \le n$），表示你希望将树以 $r$ 为根进行查询。

你将收到一个整数 $x$（$1 \le x \le n$），即当树以 $r$ 为根时，$a$ 和 $b$ 的最近公共祖先（LCA）。

当你程序确定了节点 $a$ 和 $b$ 后，请按如下格式报告答案："! a b"，其中 $a$ 和 $b$ 是两个隐藏节点；并在刷新输出流后立即正常终止程序。$a$ 和 $b$ 的输出顺序可以任意。

每次输出查询后，请务必换行并刷新输出流；否则你会收到 “Idleness limit exceeded”（空闲超时）错误。具体方法如下：

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

若在任何时候你输出了非法内容，或查询次数超过 $k$ 次，交互将立即终止，你将获得 “Wrong Answer”（错误答案）判定。非法输出包括：格式错误的查询，或输出的 $k$ 小于 $0$ 或大于 $n$。

Hack（构造测试数据）格式

要 hack 一个解答，请使用如下格式：

第一行为整数 $n$（$1 \le n \le 10^5$）。

接下来 $n-1$ 行，每行含两个整数 $u$ 和 $v$（$1 \le u,v \le n$），表示 $u$ 与 $v$ 之间的边（$u \neq v$）。这 $n-1$ 条边必须构成一棵树。

再下一行输入两个节点 $a$ 和 $b$（$1 \le a,b \le n$），以空格分隔。

最后一行输入整数 $f$（$1 \le f \le n$）。节点 $f$ 必须位于 $a$ 到 $b$ 的简单路径上（端点包含在内）。

Here is the the tree from the first sample interaction. Nodes $a$ and $b$ are highlighted.

Notice that $a$ and $b$ can be output in any order.

Additionally, here are the answers to querying every single node $1,2,\ldots,n$ for your convenience:

• $1$: $1$
• $2$: $2$
• $3$: $2$
• $4$: $4$

__________________________________________

Here is the the tree from the second sample interaction. Again, nodes $a$ and $b$ are highlighted.

Lastly, here are the answers to querying every single node $1,2,\ldots,n$ (in example $2$) for your convenience:

• $1$: $1$
• $2$: $4$
• $3$: $1$
• $4$: $4$
• $5$: $4$

以下是第一个样例交互中的树。节点 $a$ 和 $b$ 已高亮显示。

注意：$a$ 和 $b$ 的输出顺序可以任意。

此外，为方便起见，以下是对每个节点 $1,2,\ldots,n$ 进行查询所得的结果：

• $1$: $1$
• $2$: $2$
• $3$: $2$
• $4$: $4$

__________________________________________

以下是第二个样例交互中的树。同样地，节点 $a$ 和 $b$ 已高亮显示。

最后，为方便起见，以下是对示例 $2$ 中每个节点 $1,2,\ldots,n$ 进行查询所得的结果：

• $1$: $1$
• $2$: $4$
• $3$: $1$
• $4$: $4$
• $5$: $4$