Description

给定一棵包含 $n$ 个顶点的树。树是一种图，保证任意两个顶点之间恰好存在一条简单路径。同时保证至少有一个顶点与不少于 3 个顶点直接相连。 其中有一个顶点是根节点，你的任务是找出它。为此，你可以进行如下形式的询问：

• 给定一个顶点集合 $a_1, a_2, \ldots, a_m$，检查它们的最近公共祖先是否在这个集合中。

对于顶点集合 $S$，若顶点 $v$ 位于从 $S$ 中所有顶点到根的路径上，则称 $v$ 为 $S$ 的公共祖先。集合 $S$ 的最近公共祖先（LCA）是指离根最远的那个公共祖先。

交互说明

交互开始时，首先读入一个整数 $n$（$4 \leq n \leq 500$），表示顶点数量。

接着读入 $n - 1$ 行，每行包含两个整数 $a_i, b_i$（$1 \leq a_i, b_i \leq n$），表示在顶点 $a_i$ 和 $b_i$ 之间有一条边。

保证输入的 $n - 1$ 条边构成一棵树，并且至少有一个顶点的度数不小于 3。

你可以通过如下方式发起询问：先输出 "?"，再输出一个整数 $m$，然后输出 $m$ 个互不相同的整数 $a_1, a_2, \ldots, a_m$（$1 \leq m \leq n,\ 1 \leq a_i \leq n$），表示你想要检查的顶点集合。

交互器会返回 "YES"，如果它们的 LCA 属于集合 $\{a_1, a_2, \ldots, a_m\}$；否则返回 "NO"。

你最多可以询问 1000 次，但分数将取决于你的询问次数。输出最终答案不计入询问次数。请参考评分部分获取详细说明。

当你确认根节点后，输出符号 "!"，然后输出一个整数 $v$（$1 \leq v \leq n$），表示根节点。然后终止程序。

在输出每次询问后，不要忘记输出换行并刷新缓冲区。可以使用：

• 在 C++ 中使用 fflush(stdout) 或 cout.flush()；
• 在 Python 中使用 stdout.flush()。

保证对于每个测试用例，树和其根节点在交互开始前已经固定，交互器不会自适应改变。

7
4 1
1 2
4 3
3 5
3 6
4 7

NO

YES

NO

YES

? 2 5 6

? 3 6 3 5

? 2 1 7

? 2 4 6

! 4

Hint

样例说明

第一次询问：顶点 $5$ 和 $6$ 的 LCA 是顶点 $3$，不在集合 $\{5, 6\}$ 中，因此返回 "NO"。

第二次询问：顶点 $3, 5, 6$ 的 LCA 是顶点 $3$，在集合中，因此返回 "YES"。

第三次询问：顶点 $1$ 和 $7$ 的 LCA 是顶点 $4$，不在集合中，因此返回 "NO"。

第四次询问：顶点 $4$ 和 $6$ 的 LCA 是顶点 $4$，在集合中，因此返回 "YES"。

由此可以推测根节点是顶点 $4$，这就是正确答案。

评分规则

1. （7 分）：$n \leq 9$
2. （10 分）：$n \leq 30$
3. （最高 83 分）：$n \leq 500$

在前两个子任务中，你最多可以询问 1000 次。

在第三个子任务中，设 $k$ 为你在某个测试用例中使用的最大询问次数：

• 如果 $k \leq 9$，你将得到 83 分。
• 否则，你将得到：$$\left\lfloor \max \left(10,\ 83 \cdot \left(1 - \frac{\ln(k - 6)}{7}\right)\right) \right\rfloor$$

以下是 C++ 代码实现的计分函数：

((k <= 9) ? 83 : max(10, int(83 * (1 - log(k - 6.0) / 7))))

翻译由 ChatGPT-5 完成