AT_tkppc4_2_l.建物と魔女

E869120 君对帕研王国的城市布局非常感兴趣。然而，由于帕研王国受到魔法的封锁，他无法直接获取道路连接的信息。为此，他打算通过大总统 Segtree 提出一些问题来进一步了解国内城市之间的道路连接。

他可以使用以下方式进行询问：

1. 指定一个长度为 $N$ 的排列 $p$，其中包含从 $1$ 到 $N$ 的每个整数，并且每个整数仅出现一次。
2. 要求 Segtree 使用魔法将每个城市的建筑物高度设定为 $2^{p_i - 1}$。
3. 接着，指定一个 $0$ 到 $2^N - 1$ 之间的数 $x$，询问满足条件的城市对 $(u, v)$ 的数量 $e$：
   • 从 $u$ 到 $v$ 的最短路径上经过的建筑物的高度和至少是 $x$。

例如，当帕研王国结构如图所示，给定排列 $p = \{1, 5, 3, 4, 2\}$ 和 $x = 21$ 时：

• 城市的建筑物高度分别为 $\{1, 16, 4, 8, 2\}$。
• 满足条件的城市对有 $(1, 3), (1, 4), (1, 5), (2, 4), (2, 5), (3, 4), (3, 5)$，共 7 对，因此 Segtree 将返回 7。
• 例如，从城市 1 到 5 的最短路径上经过的建筑物的高度和为 $1 + 16 + 8 + 2 = 27$，满足大于等于 21 的条件。

由于太多的询问可能会激怒帕研王国的军队和Segtree，E869120 君希望尽可能减少询问次数。他的目标是在不超过 3600 次询问的前提下，找出帕研王国的所有城市连接关系。然而，这个问题对他来说太复杂了。他需要你设计一个程序，帮助他用尽量少的询问次数破解帕研王国的城市连接结构。

输入格式

这是一个交互式问题，输入输出格式与常规题目不同，请注意。

首先，你需要从系统获取城市数量 $N$。

$N$

然后反复执行以下步骤，直到找到帕研王国的城市连接结构：

1. 向 Segtree（裁判系统）提问，格式如下：

   ? $p_1$ $p_2$ ... $p_N$ $x$

   你需要在一行输出 '?'，然后紧接着输出 $N + 1$ 个整数，排列 $p$ 和整数 $x$。排列 $p$ 必须包含 $1$ 到 $N$ 的所有整数，并且每个整数仅出现一次，$x$ 是 $0$ 到 $2^N - 1$ 之间的数。输出后别忘了换行。

2. Segtree 会给出回答，即一个整数 $e$。请读取此数。

   注意：如果询问次数超过 3600 次，裁判将返回 -1。若出现 -1，请立即终止程序。如果在超过询问次数后未终止程序，其行为是未定义的。

3. 当掌握了帕研王国的城市连接结构后，以以下格式输出结果：

   ! $a_1$ $b_1$ $a_2$ $b_2$ ... $a_{N-1}$ $b_{N-1}$

   输出 $N - 1$ 行，每行两个整数 $a_i$ 和 $b_i$，表示第 $i$ 条连接的是城市 $a_i$ 和 $b_i$。输出顺序可任意，$a_i$ 和 $b_i$ 的顺序也可颠倒。例如，若城市连接为 $(1, 2), (2, 3), (3, 4)$，你可以输出：

   3 2
   1 2
   4 3
   

数据范围与提示

• $1 \leq N \leq 60$
• 帕研王国为连通的树结构，即任意两个城市之间通过道路可达。

子任务

共两个子任务：

1. (100 分) $N \leq 4$
2. (1200 分) $5 \leq N \leq 60$，根据最大询问次数 $Q$ 决定得分。

最大询问次数 $Q$	得分 ($1,200$ 满分)
$2001 \leq Q \leq 3600$	310 分
$1721 \leq Q \leq 2000$	420 分
$1101 \leq Q \leq 1720$	550 分
$601 \leq Q \leq 1100$	$1200-(Q-600)$ 分
$Q \leq 600$	1200 分

注意事项

• 输出格式错误可能导致裁判行为不定义（不一定是 WA）。
• 每次输出后必须立即 flush，否则可能会导致 TLE。
• 禁止超过 3600 次询问，超出后未终止程序的后果未知。
• 即使所有测试均 AC，部分题目仍需通过更少询问次数才能获得满分。

输入输出示例 1

以下示例中的 $N = 4$，帕研王国的城市连接如图所示：

程序输入（裁判输出）	程序输出
4
? 1 2 3 4 8	3
? 4 3 2 1 15	1
!
1 2
2 4
1 3

本翻译由 AI 自动生成