AT_pakencamp_2025_day2_h Sunk Islands
题目描述
**本题为交互题。**
在“パ研洋”上漂浮着 $N$ 个岛屿，编号为 $1,2,\dots,N$。
还有 $N-1$ 座桥，第 $i$ 条桥连接岛屿 $U_i$ 和 $V_i$。这里，任意一个岛屿都可以通过某些桥经过若干次抵达其他任意岛屿。
“K 运営長”打算将这些岛屿全部纳入自己的支配，但他并不知道桥的结构。因此，他打算多次向了解桥结构的“パンサーカメレオン”的パ太郎提问，以此推断出桥的连接方式。
提问流程如下：
1. “K 运営長”选择 1 个及以上、最多 $N$ 个岛屿，并告知パ太郎。
2. パ太郎会按照以下要求，在这 $N$ 个岛屿中沉没一些岛屿，然后告诉 K 运営長最多能保留下多少座未被沉没的岛屿。
- 所有未被沉没的岛屿，必须都包含在 K 运営長选择的集合内。
- 保留下来的所有岛屿必须构成连通块，即任意两个保留下来的岛屿间，都可以通过桥经过若干次到达。
- 任意一个保留下来的岛屿，其相邻未沉没的岛屿不超过 2 个。
注意，这是パ太郎的思想实验，实际不会将岛屿沉没。
但由于パ太郎也很忙，他最多只会回答 $L$ 次提问。
给定岛屿数和允许向パ太郎提问的最大次数，要求编程实现 K 运営長推断所有桥连接关系的策略。
输入格式
首先，标准输入给出 $N,L$。
```
N L
```
接下来，你可以与パ太郎进行至多 $L$ 次交互，每次提问的输出格式如下：
假设你选择的岛屿集合为 $s_1,s_2,\dots,s_n$，则应输出：
```
? n s_1 s_2 ... s_n
```
之后，パ太郎会返回整数 $X$，输入格式如下：
```
X
```
这里 $X$ 含义如下：
- 若 $X\ne -1$，则表示回答为 $X$。
- 若 $X=-1$，则表示你提问的次数超过了 $L$ 次，或者提问格式不正确。
- 此时，程序已被判为不正确，请立即终止程序。
当你确定得出了所有桥的整体结构之后，请按如下格式在一行内输出，且该输出不计入次数限制：
```
! u_1 v_1 u_2 v_2 ... u_{N-1} v_{N-1}
```
其中每对 $u_i,v_i$ 表示一座桥连接的两个岛屿，且同一座桥不可重复输出。输出后，程序需立即终止。
如任一次输出不满足上述任何规定，会收到输入 `-1`。
```
-1
```
此时程序已被判为错误，请立即终止程序。
输出格式
见上文描述。
说明/提示
## 子任务
1. （5 分） $L=33000$
2. （25 分） $L=10000$
3. （20 分） $L=6400$
4. （50 分） $L=4600$
## 注意事项
- **每次输出后，都要在末尾加上换行并立刻刷新输出缓冲区，否则可能会因 TLE 被判超时。**
- 当输出答案或收到 `-1` 时，请立即终止程序，否则结果不可预期。
- 多余的换行被视为输出格式不正确。
- **评测环境为非自适应（non-adaptive）**，即所有岛屿的桥连接在对话开始前就已确定，不会因过程中交互而改变。
## 输入输出样例说明
以 $N=5, U=(1,2,2,2), V=(2,3,4,5), L=10$ 为例，交互示例如下：
| 输入输出 | 内容 | 说明 |
| ---------------| --------------------------------------- | ------------------------------------------------------ |
| 输入 | `5 10` | 首先输入 $N,L$ |
| 输出 | `? 2 1 2` | 向パ太郎提问 $s=\{1,2\}$ |
| 输入 | `2` | 保留 $1,2$，沉没其他岛屿，最大为 2 |
| 输出 | `? 4 1 3 4 5` | 提问 $s=\{1,3,4,5\}$ |
| 输入 | `1` | 只可保留 $1$，沉没其他岛屿 |
| 输出 | `? 4 2 3 4 5` | 提问 $s=\{2,3,4,5\}$ |
| 输入 | `3` | 可保留 $2,3,4$，沉没 $5$ |
| 输出 | `! 1 2 3 2 5 2 2 4` | 提交答案并终止程序。 |
请注意，这只是交互的一种示例，未必足以推断所有桥的结构，且该组数据不一定符合实际评测数据的约束条件。
## 数据范围
- $N = 256$
- $1 \leq U_i,V_i\leq N\quad(1\leq i\leq N-1)$
- 任意两个岛屿均可经若干桥直达对方。
由 ChatGPT 5 翻译