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 自动生成**
输入格式
无
输出格式
无
说明/提示
### 制約
- $ 1\ \leq\ N\ \leq\ 60 $
- パ研王国は連結な木構造を成す。つまり、任意の都市から任意の都市まで道を辿って行くことが出来る。
### 小課題
この課題には、$ 2 $ 個の小課題があります。
1. (100 点) $ N\ \leq\ 4 $ を満たす。
2. (1200 点) $ 5\ \leq\ N\ \leq\ 60 $ を満たす。
ただし、小課題 $ 2 $ においては、質問回数の最大値 $ Q $ によって得点が決まります。
質問回数の最大値 $ Q $ 小課題 $ 2 $ の得点 ($ 1\ 200 $ 点満点) $ 2\ 001\ \leq\ Q\ \leq\ 3\ 600 $ $ 310 $ $ 1\ 721\ \leq\ Q\ \leq\ 2\ 000 $ $ 420 $ $ 1\ 101\ \leq\ Q\ \leq\ 1\ 720 $ $ 550 $ $ 601\ \leq\ Q\ \leq\ 1\ 100 $ $ 1\ 200\ -\ (Q\ -\ 600) $ $ Q\ \leq\ 600 $ $ 1\ 200 $### 注意
**出力形式を間違えた場合のジャッジの挙動は不定です。(WA とは限りません。)**
**また、出力の最後に flush しなければならず、そうしない場合 TLE となる場合がございます。**
**E869120 君 は、$ 3\ 600 $ 回を超える質問をしてはなりません。この回数の質問を超えてもなおプログラムを打ち切らない場合の挙動は不定です。**
**なお、AC となった場合でも満点が取れていない場合があることにご注意ください。小課題 $ 1 $, $ 2 $ 全てのテストケースにおいて $ 3\ 600 $ 回以内の質問で答えが求まれば、たとえ部分点であっても AC と出ます。**
### 入出力例 1
この入力例は、$ N\ =\ 4 $ であり、パ研王国が以下のような構造である場合のジャッジ側とのやり取りの例である。
自分のプログラムへの入力（ジャッジ側の出力） 自分のプログラムの出力 4 ? 1 2 3 4 8 3 ? 4 3 2 1 15 1 !
1 2
2 4
1 3