问题描述

这是一个交互式问题。

dwango公司员工的"尼万君"住在一棵有 $N$ 个顶点的树上。这棵树的每个顶点都有从 $1$ 到 $N$ 的编号。这棵树的第 $i$ 条边是连接顶点 $a_i$ 和顶点 $b_i$ 的双向长度为 $1$ 的边。"尼万君"知道 每个顶点的度数都不超过 $5$。

"尼万君"的家位于这棵树的某个顶点，但他忘记了家在哪里。

"尼万君"希望通过他自己编写的程序最多进行 $Q$ 次询问，以确定家所在的顶点。当将 $2$ 个顶点的编号 $u,v$ 传递给程序时，会显示距离较近的顶点的编号。然而，如果两个顶点与家所在的顶点的距离相等，将显示 0。

约束条件

• $2 \leq N \leq 2{,}000$
• $Q = 14$
• $1 \leq a_i,b_i \leq N$
• 给定的图是一棵树
• 每个顶点的度数都不超过 $5$

---

部分分

• 如果在每个顶点的度数都不超过 $2$ 的数据集上给出正确答案，将获得 $400$ 分。

输入输出

首先，从标准输入读入以下格式的输入：

$N$ $Q$ $a_1$ $b_1$ $:$ $a_{N-1}$ $b_{N-1}$

然后，以以下格式输出问题：

? $u$ $v$

其中，$u,v$ 必须是 $1$ 到 $N$ 之间的整数。然后，问题的答案以以下格式从标准输入给出：

$ans$

其中，$ans$ 是 $u,v,0$ 中的一个。每个值表示以下情况：

• $u$：$u$ 和 $v$ 中更接近家所在的顶点的是 $u$
• $v$：$u$ 和 $v$ 中更接近家所在的顶点的是 $v$
• $0$：$u$ 和 $v$ 与家所在的顶点的距离相等

最后，以以下格式输出答案：

! $x$

其中，$x$ 必须是家所在的顶点。

---

评判

• 在输出之后，请刷新标准输出。 如果不遵守此规则，可能会导致超时错误。
• 在输出答案后，请立即结束程序。如果不遵守此规则，则评判行为未定义。
• 未定义输出答案错误时的行为（不一定是 WA）。

示例

这是在下面的树中，如果尼万君的家位于顶点 $3$ 的情况下的输入输出示例。

输入

输出

6 14
1 2
5 2
3 1
3 6
1 4

? 4 5

4

? 1 6

0

? 6 5

6

! 3

• 在顶点 $4,5$ 中，离顶点 $3$ 更近的是顶点 $4$，因此显示 $4$。
• 顶点 $1,6$ 与顶点 $3$ 的距离相等，因此显示 $0$。
• 在顶点 $6,5$ 中，离顶点 $3$ 更近的是顶点 $6$，因此显示 $6$。
• 答案回答家所在的顶点是 $3$。通过最多 $14$ 次问题输出了正确答案，因此是正确的答案。