这是一个交互问题!
在上届地区比赛 Hemose 中,Carpe Diem 团队成员 ZeyadKhattab 和 YahiaSherif 由于某些未知原因没有获得 ICPC 资格。 Hemose 非常伤心,赛后度过了糟糕的一天,但 ZeyadKhattab 非常明智,非常了解 Hemose,不想看到他伤心。
Zeyad 知道 Hemose 喜欢树问题,所以他用一个非常特殊的设备给了他一个树问题。
Hemose 有一个带 $$$n$$$ 节点和 $$$n-1$$$ 边的加权树。不幸的是,Hemose 不记得边的权重。
让我们将 $$$u\neq v$$$ 的 $$$Dist(u, v)$$$ 定义为从节点 $$$u$$$ 到节点 $$$v$$$ 的路径上所有边的权重的最大公约数。
Hemose 有一个特殊的装置。 Hemose 可以为设备提供一组节点,设备将返回该组中任意两个节点之间最大的 $$$Dist$$$。更正式地说,如果 Hemose 为设备提供一组 $$$S$$$ 节点,则设备将返回所有对 $$$(u, v)$$$ 中 $$$Dist(u, v)$$$ 的最大值,其中 $$$u$$$、$$$v$$$ $$$\in$$$ $$$S$$$ 和 $$$u \neq v$$$。
Hemose 最多可以使用该设备 $$$12$$$ 次,并且想要找到任意两个不同的节点 $$$a$$$, $$$b$$$,使得 $$$Dist(a, b)$$$ 是最大可能的。你能帮助他吗?
互动
从读取单个整数 $$$n$$$ ($$$2 \le n \le 10^3$$$) 开始交互 - 树中的节点数。
接下来,读取 $$$n-1$$$ 行。
接下来的 $$$n-1$$$ 行中的第 $$$i$$$ 包含两个整数 $$$u_i$$$ 和 $$$v_i$$$ ($$$1 \leq u_i, v_i \leq n$$$, $$$u_i\neq v_i$$$),这意味着节点 $$$u_i$$$ 和 $$$u_i$$$ 之间有一条边$$$v_i$$$。
保证边的权重为$$$\leq 10^9$$$。
保证给定的图是一棵树。
现在您可以开始提问。要询问一组 $$$k$$$ 节点 $$$v_1, v_2, \ldots, v_k$$$($$$2 \le k \le n$$$, $$$1 \le v_i \le n$$$,所有 $$$v_i$$$ 都是不同的),输出:
? $$$k$$$ $$$v_1$$$ $$$v_2$$$ $$$\ldots$$$ $$$v_k$$$
然后您将收到一个整数 $$$x$$$,即 $$$1 \le i, j \le k$$$ 和 $$$i \neq j$$$ 上最大的 $$$Dist(v_i, v_j)$$$。
当您找到 $$$a$$$ 和 $$$b$$$ ($$$1 \le a, b \le n)$$$, $$$a\neq b$$$) 使得 $$$Dist(a, b)$$$ 是可能的最大值时,按以下格式打印答案:
! $$$a$$$$$$b$$$
输出答案不计入 $$$12$$$ 查询的限制。
如果有多对 $$$(a, b)$$$ 具有相同的最大 $$$Dist(a, b)$$$,则可以输出任何一个。
打印查询后,不要忘记输出行尾并刷新输出。否则,您将超出空闲限制。为此,请使用:
- C++ 中的 fflush(stdout) 或 cout.flush();
- Java 中的 System.out.flush();
- 帕斯卡刷新(输出);
- Python 中的 stdout.flush() ;
- 请参阅其他语言的文档。
黑客
要破解解决方案,请使用以下格式。
第一行应包含一个整数 $$$n$$$ $$$(2 \leq n \le 10^3)$$$ — 节点数。
接下来的 $$$n-1$$$ 行中的第 $$$i$$$ 应包含三个整数 $$$u_i$$$, $$$v_i$$$, $$$w_i$$$ ($$$1 \le u_i, v_i \le n$$$, $$$u_i\ne v_i$$$, $$$1 \le w \le 10^9$$$),这意味着节点 $$$u_i$$$ 和 $$$v_i$$$ 之间有一条边,权重为 $$$w_i$$$。
这些 $$$n-1$$$ 边必须形成一棵树。
示例
输入 #1
6 1 2 2 3 2 4 1 5 5 6 10 2 10
输出 #1
? 6 1 2 3 4 5 6 ? 3 3 1 5 ? 2 1 2 ! 1 2
注意
第一个样本中的树: