有一个隐藏的树,有 $$$n$$$ 个顶点。树的 $$$n-1$$$ 边从 $$$1$$$ 到 $$$n-1$$$ 编号。您可以提出以下两种类型的查询:
1. 为评分者提供一个数组 $$$a$$$,其中包含 $$$n - 1$$$ 正整数。对于从 $$$1$$$ 到 $$$n - 1$$$ 的每条边,边 $$$i$$$ 的权重设置为 $$$a_i$$$。然后,分级机将返回直径$$$^\dagger$$$的长度。
2. 给评分者两个索引 $$$1 \le a, b \le n - 1$$$。分级器将返回边 $$$a$$$ 和 $$$b$$$ 之间的边数。换句话说,如果边 $$$a$$$ 连接 $$$u_a$$$ 和 $$$v_a$$$,而边 $$$b$$$ 连接 $$$u_b$$$ 和 $$$v_b$$$,则评分器将返回 $$$\min(\text{dist}(u_a, u_b), \text{dist}(v_a, u_b), \text{dist}(u_a, v_b), \text{dist}(v_a, v_b))$$$,其中 $$$\text{dist}(u, v)$$$ 表示顶点 $$$u$$$ 和 $$$v$$$ 之间路径上的边数。
在最多 $$$n$$$ 类型 1 查询和 $$$n$$$ 类型 2 查询(以任意顺序)之后,找到与隐藏树同构 $$$^\ddagger$$$ 的任何树。
$$$^\dagger$$$ 两个顶点之间的距离是连接它们的唯一简单路径上的权重之和。直径是所有这些距离中最大的。
$$$^\ddagger$$$ 如果存在包含从 $$$1$$$ 到 $$$n$$$ 的整数的排列 $$$p$$$,使得边 ($$$u$$$, $$$v$$$) 出现在第一棵树中当且仅当边($$$p_u$$$, $$$p_v$$$) 出现在第二棵树中。
输入
输入的第一行也是唯一一行包含一个整数 $$$n$$$ ($$$3 \le n \le 1000$$$) — 树中的顶点数。
互动
通过阅读 $$$n$$$ 开始交互。
您可以通过以下方式进行查询:
1. "$$$\mathtt{?}\,1\,a_1\,a_2 \ldots a_{n-1}$$$" ($$$1 \le a_i \le 10^9$$$)。然后,您应该读取一个整数$$$k$$$,它表示直径的长度。您最多只能询问此查询 $$$n$$$ 次。
2. "$$$\mathtt{?}\,2\,a\,b$$$" ($$$1 \le a, b \le n - 1$$$)。然后,您应该读取一个整数 $$$k$$$,它表示边 $$$a$$$ 和 $$$b$$$ 之间的边数。您最多只能询问此查询 $$$n$$$ 次。
如果您的查询无效。该程序将立即终止,您将收到错误答案判决。
要给出最终答案,请打印“!”在一行上,后跟 $$$n - 1$$$ 行,其中 $$$i$$$ 行包含“$$$u_i\,v_i$$$” ($$$1 \le u_i, v_i \le n$$$),这表示对于从 $$$1$$$ 到 $$$n-1$$$ 的每个 $$$i$$$,$$$u_i$$$ 和 $$$u_i$$$ 之间有一条边$$$v_i$$$。
打印查询后,不要忘记输出行尾并刷新输出。否则,您将超出空闲限制。为此,请使用:
- C++ 中的 fflush(stdout) 或 cout.flush();
- Java 中的 System.out.flush();
- 帕斯卡刷新(输出);
- Python 中的 stdout.flush() ;
- 请参阅其他语言的文档。
黑客
第一行包含一个整数 $$$n$$$ ($$$3 \le n \le 1000$$$) — 树中的顶点数。
接下来的 $$$n - 1$$$ 行包含两个整数,每个 $$$u_i, v_i$$$ ($$$1 \le u_i, v_i \le n$$$) - 树的边缘。
示例
输入 #1
5 3 1 9 0
输出 #1
? 1 1 1 1 1 ? 2 1 3 ? 1 4 3 2 1 ? 2 4 2 ! 3 1 4 2 1 2 2 5
注意
示例中的隐藏树如上所示。顶点上的数字表示顶点编号,边上的数字表示边编号。
在第一个查询中,所有边都设置为权重 $$$1$$$,因此直径的长度为 $$$3$$$,如图所示。
在第二个查询中,边 $$$1$$$ 和 $$$3$$$ 之间有 $$$1$$$ 边。
在第三个查询中,通过取边 $$$1$$$、$$$2$$$ 和 $$$3$$$,直径为 $$$9$$$。
在第四个查询中,边 $$$4$$$ 和 $$$2$$$ 之间没有边。
示例中给出的答案如上图所示。由于它与隐藏树同构,因此它被接受为正确答案。请注意,边缘可以按任何顺序打印。