CF1592D.Hemose in ICPC ?

This is an interactive problem!

In the last regional contest Hemose, ZeyadKhattab and YahiaSherif — members of the team Carpe Diem — did not qualify to ICPC because of some unknown reasons. Hemose was very sad and had a bad day after the contest, but ZeyadKhattab is very wise and knows Hemose very well, and does not want to see him sad.

Zeyad knows that Hemose loves tree problems, so he gave him a tree problem with a very special device.

Hemose has a weighted tree with $n$ nodes and $n-1$ edges. Unfortunately, Hemose doesn't remember the weights of edges.

Let's define $Dist(u, v)$ for $u\neq v$ as the greatest common divisor of the weights of all edges on the path from node $u$ to node $v$.

Hemose has a special device. Hemose can give the device a set of nodes, and the device will return the largest $Dist$ between any two nodes from the set. More formally, if Hemose gives the device a set $S$ of nodes, the device will return the largest value of $Dist(u, v)$ over all pairs $(u, v)$ with $u$, $v$ $\in$ $S$ and $u \neq v$.

Hemose can use this Device at most $12$ times, and wants to find any two distinct nodes $a$, $b$, such that $Dist(a, b)$ is maximum possible. Can you help him?

Interaction

Begin the interaction from reading a single integer $n$ ($2 \le n \le 10^3$) — the number of nodes in the tree.

Next, read $n-1$ lines.

The $i$-th of the next $n-1$ lines contains two integers $u_i$ and $v_i$ ($1 \leq u_i, v_i \leq n$, $u_i\neq v_i$), which means that there's an edge between nodes $u_i$ and $v_i$.

It's guaranteed that weights of edges were $\leq 10^9$.

It is guaranteed that the given graph is a tree.

Now you may begin asking queries. To ask a query about a set of $k$ nodes $v_1, v_2, \ldots, v_k$ ($2 \le k \le n$, $1 \le v_i \le n$, all $v_i$ are distinct), output:

? $k$ $v_1$ $v_2$ $\ldots$ $v_k$

You will then receive an integer $x$, the largest $Dist(v_i, v_j)$ over $1 \le i, j \le k$ with $i \neq j$.

When you have found $a$ and $b$ ($1 \le a, b \le n)$, $a\neq b$) such that $Dist(a, b)$ is the maximum possible, print the answer in the following format:

! $a$ $b$

Outputting answer doesn't count towards the limit of $12$ queries.

If there are several pairs $(a, b)$ with the same largest $Dist(a, b)$, you can output any.

After printing a query do not forget to output the 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 the documentation for other languages.

Hacks

To hack a solution, use the following format.

The first line should contain a single integer $n$ $(2 \leq n \le 10^3)$ — the number of nodes.

The $i$-th of the next $n-1$ lines should contain three integers $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$), which means that there's an edge between nodes $u_i$ and $v_i$ with weight $w_i$.

These $n-1$ edges must form a tree.

这是一个交互式问题！

在上一届区域赛中，Hemose、ZeyadKhattab 和 YahiaSherif —— 队伍 Carpe Diem 的成员 —— 因某些未知原因未能晋级 ICPC。Hemose 非常难过，赛后心情十分低落；但 ZeyadKhattab 非常睿智，且非常了解 Hemose，因此他不愿看到 Hemose 沮丧。

Zeyad 知道 Hemose 喜欢树相关的问题，于是给了他一道关于树的题目，并配备了一个非常特殊的设备。

Hemose 有一棵含 $n$ 个节点、$n-1$ 条边的带权树。不幸的是，Hemose 已经记不清各条边的权重了。

我们定义：对任意 $u \neq v$，$Dist(u, v)$ 表示从节点 $u$ 到节点 $v$ 的路径上所有边的权重的最大公约数（GCD）。

Hemose 拥有一个特殊设备。他可以向该设备输入一个节点集合，设备将返回该集合中任意两个节点之间的最大 $Dist$ 值。更准确地说，若 Hemose 向设备输入节点集合 $S$，则设备将返回所有满足 $u, v \in S$ 且 $u \neq v$ 的二元组 $(u, v)$ 中最大的 $Dist(u, v)$ 值。

Hemose 最多可使用该设备 $12$ 次，目标是找出任意两个不同的节点 $a$、$b$，使得 $Dist(a, b)$ 达到可能的最大值。你能帮他实现吗？

交互流程

首先，读入一个整数 $n$（$2 \le n \le 10^3$），表示树中节点的数量。

接着，读入 $n-1$ 行。

第 $i$ 行包含两个整数 $u_i$ 和 $v_i$（$1 \leq u_i, v_i \leq n$，$u_i \neq v_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$ 的二元组 $(v_i, v_j)$ 中最大的 $Dist(v_i, v_j)$ 值。

当你找到一对节点 $a$ 和 $b$（$1 \le a, b \le n$，$a \neq b$），使得 $Dist(a, b)$ 达到可能的最大值时，请按如下格式输出答案：

! $a$ $b$

输出答案不计入 $12$ 次查询次数限制。

若存在多个满足最大 $Dist(a,b)$ 的节点对 $(a,b)$，输出其中任意一对即可。

每次输出查询后，请务必输出换行符并刷新输出缓冲区，否则将得到 “Idleness limit exceeded”（空闲超时）错误。为此，请使用：

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

Hack（构造测试数据）

要 hack 一个解法，请使用以下格式：

第一行应为一个整数 $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_i \le 10^9$），表示节点 $u_i$ 与 $v_i$ 之间存在一条权重为 $w_i$ 的边。

这 $n-1$ 条边必须构成一棵树。

The tree in the first sample:

第一个样例中的树：