CF2061G.Kevin and Teams

这是一道交互题。

Kevin 有 $n$ 个同学，编号为 $1, 2, \ldots, n$。他们之间可能是朋友，也可能不是朋友。

Kevin 想要选出 $2k$ 个同学组成 $k$ 支队伍，每支队伍恰好包含 $2$ 人。每个同学最多只能属于一支队伍。

设第 $i$ 支队伍中的两人为 $u_i$ 和 $v_i$。为了避免组队过程中潜在的冲突，队伍成员必须满足以下两个条件之一：

• 对于所有 $i$（$1 \leq i \leq k$），同学 $u_i$ 和 $v_i$ 是朋友。
• 对于所有 $i$（$1 \leq i \leq k$），同学 $u_i$ 和 $v_i$ 不是朋友。

Kevin 想要确定最大的 $k$，使得无论这 $n$ 个人之间的朋友关系如何，他总能找到 $2k$ 人组成队伍。之后，他需要组成这 $k$ 支队伍。但询问两个同学是否是朋友很尴尬，因此 Kevin 希望在使用不超过 $n$ 次询问的情况下达成目标。

交互器是自适应的。这意味着同学之间的隐藏关系在交互前并不固定，并且会在交互过程中改变。

每个测试包含多个测试用例。第一行包含测试用例数量 $t$（$1 \le t \le 10^4$）。接下来是各个测试用例的描述。

每个测试用例的第一行包含一个正整数 $n$（$2 \leq n \leq 10^5$）—— 同学的数量。

首先，你需要输出一个整数 $k$（$1 \leq k \leq \frac{n}{2}$）—— 你能组成的最大队伍数量。

你可以通过以下方式进行查询：输出一行格式为 ? u v 的内容，其中 $1 \leq u \neq v \leq n$。之后，读取一个整数：$0$ 或 $1$，表示他们是否是朋友。$1$ 表示是朋友，$0$ 表示不是朋友。

如果你想要输出答案，请输出 ! u1 v1 u2 v2 … uk vk。你需要输出恰好 $2k$ 个不同的数字。然后，交互将继续进行下一个测试用例。

你最多可以进行 $n$ 次查询。输出答案不计入查询次数。

保证所有测试用例的 $n$ 之和不超过 $10^5$。

每次输出查询后，请不要忘记换行并刷新输出$^{\text{∗}}$。否则，你将得到 Idleness limit exceeded 结果。

如果在任何交互步骤中读取到 $-1$ 而非有效数据，你的程序必须立即退出。这意味着你的程序将因无效查询或其他错误而收到 Wrong answer。未能退出可能导致任意结果，因为你的程序将继续从已关闭的流中读取。

Hack 方式

用于 Hack 的交互器不是自适应的。要创建 Hack，请使用以下格式。

第一行包含单词 "manual"。

第二行包含一个整数 $t$（$1 \leq t \leq 10^4$）—— 测试用例数量。

每个测试用例的第一行包含一个整数 $n$（$2 \leq n \leq 10^5$）—— 同学的数量。

每个测试用例的第二行包含一个由 '0' 和 '1' 组成的字符串 $s$，长度为 $\frac{n(n - 1)}{2}$ —— 表示 $(1, 2)$、$(1, 3)$、$\ldots$、$(1, n)$、$(2, 3)$、$(2, 4)$、$\ldots$、$(2, n)$、$\ldots$、$(n - 1, n)$ 之间的关系。'1' 表示是朋友，'0' 表示不是朋友。

以下是示例输入：

manual
2
3
011
5
1011101011

所有测试用例的 $n$ 之和不得超过 $10^5$。

Hack 还有一个额外限制：所有测试用例的 $\frac{n(n-1)}{2}$ 之和不得超过 $10^7$。

$^{\text{∗}}$ 要刷新输出，请使用：

• C++ 中的 fflush(stdout) 或 cout.flush()；
• Python 中的 sys.stdout.flush()；
• 其他语言请参考文档。

第一个测试用例：

Kevin 声称无论 3 人之间的朋友关系如何，他总能组成 1 支队伍。

Kevin 询问同学 1 和 2 是否是朋友。裁判回答他们是朋友。

Kevin 回答他可以组成由同学 1 和 2 组成的队伍。

第二个测试用例：

Kevin 声称无论 5 人之间的朋友关系如何，他总能组成 2 支队伍。

Kevin 询问了同学 $(1, 2)$、$(3, 4)$、$(3, 5)$、$(1, 3)$、$(2, 4)$ 之间的关系。裁判依次回答 $1, 0, 1, 0, 0$。

Kevin 回答他可以组成两支队伍 $(1, 2)$ 和 $(3, 5)$。

也可以组成两支队伍 $(1, 3)$ 和 $(2, 4)$，因为他们都彼此不是朋友。

翻译由 DeepSeek R1 完成