【MX-S3-T3】「FeOI Round 1」再演


**这是一道交互题。** jt 有一个大小为 $n$ 的集合 $S$，集合中每个元素都是一个无序二元整数对 $(x, y)$，保证集合中 $1 \sim 2n$ 共 $2n$ 个整数每个恰好出现一次。 比如当 $n = 3$ 时，合法的集合 $S$ 可能是 $\{(1, 5), (2, 3), (4, 6)\}$。 开始时你只知道 $n$ 而不知道 $S$ 具体是什么。 现在支持一种操作：你可以给出 $i, j$（$1 \le i, j \le 2n$），然后 jt 会交换 $i, j$ 在 $S$ 中的位置（如 $i, j$ 在同一个二元组内，或 $i = j$，则什么也不会发生）。 比如，当 $S = \{(1, 5), (2, 3), (4, 6)\}$ 时，执行 $i = 2, j = 6$ 后 $S = \{(1, 5), (6, 3), (4, 2)\} = \{(1, 5), (2, 4), (3, 6)\}$。 在最开始时以及每次操作过后，对于当前的集合 $S$，jt 会告诉你 $res = \min\limits_{(x, y) \in S} \max(x, y)$。 比如，当 $S = \{(1, 5), (2, 3), (4, 6)\}$ 时，$res$ 为 $\min(\max(1, 5), \max(2, 3), \max(4, 6)) = \min(5, 3, 6) = 3$。 注意，每次 jt 告诉你 $res$ 之后**不会撤销**你做的操作，即你的操作是持续有效的。 你需要在 $lim$ 次操作内猜出**初始的**集合 $S$，即进行所有交换操作之前的版本。 保证初始的 $S$ 是提前确定的，即**交互库不自适应**。 ### 交互方式 **本题单个测试点内包含多组数据。** 首先读入数据组数 $T$。 接下来有 $T$ 组数据，对于每组数据进行以下过程： 输入 $S$ 的大小 $n$ 以及 $lim$ 以开始交互。 每次操作，首先读入 $res$，接下来输出一行 `^ i j` 表示你要执行操作 $i, j$。 在你确定答案后，请先输出一行一个 `!`，然后接下来 $n$ 行每行输出两个整数 `x y` 代表 $S$ 中的一个二元组，然后准备读入下一组数据。你可以以任意顺序输出这些二元组，且二元组内元素顺序可以任意。 每次在你输出一行后，请清空缓冲区： - 在 C++ 中，使用 `fflush(stdout)` 或 `cout.flush()`。 - 在 Pascal 中，使用 `flush(output)`。 - 在 Python 中，使用 `stdout.flush()`。 - 其它语言请自行查阅文档。 **当你在单个测试点所有测试数据的总操作次数不超过 $\boldsymbol{2.5 \times 10^5}$ 次时**，保证交互库占用时间不超过 $1\operatorname s$，空间不超过 $128\operatorname{MB}$，也就是你至少能使用 $1 \operatorname{s}$ 的时间以及 $384\operatorname{MB}$ 的空间。

见「交互方式」。

见「交互方式」。

2
3 100
3

3

4

2




1 0
2

^ 1 2

^ 3 6

^ 6 2

!
5 1
6 4
2 3


!
1 2

**【样例解释】** 注意，样例只是描述了一个可能发生的交互过程，**并不一定存在逻辑**（就是说答案可能是乱猜猜对的）。 对于第一组测试数据，$S$ 最开始为 $\{(1, 5), (2, 3), (4, 6)\}$，jt 告诉你 $res = 3$。 接下来你交换 $1, 2$，$S$ 变为 $\{(2, 5), (1, 3), (4, 6)\}$，jt 告诉你 $res = 3$。 接下来你交换 $3, 6$，$S$ 变为 $\{(2, 5), (1, 6), (3, 4)\}$，jt 告诉你 $res = 4$。 接下来你交换 $6, 2$，$S$ 变为 $\{(5, 6), (1, 2), (3, 4)\}$，jt 告诉你 $res = 2$。 你输出 $\{(5, 1), (6, 4), (2, 3)\}$，用了 $3$ 次操作，不超过 $lim = 100$ 次，回答正确。 对于第二组测试数据，$S$ 初始为 $\{(1, 2)\}$，你直接输出 $\{(1, 2)\}$，用了 $0$ 次操作，不超过 $lim = 0$ 次，回答正确。 **【数据范围】** **本题开启捆绑测试。** 记 $\sum n$ 为单个测试点内所有的 $n$ 之和。 对于 $100\%$ 的数据，$1 \le T \le 10^5$，$ 1 \le n \le 5 \times 10^4$，$ \sum n \le 10^5$。 | 子任务编号 | $T$ | $n$ | $lim$ | 分数 | | :-: | :-: | :-: | :-: | :-: | | $1$ | $=1$ | $=1$ | $=0$ | $1$ | | $i$（$2 \le i \le 6$） | $=(2i-1)!!$ | $=i$ | $=10^9$ | $8$ | | $7$ | $\le 5$ | $\le 100$ | $=5n^2$ | $14$ | | $8$ | $\le 25$| $\le 10^3$ | $=10n$ | $15$ | | $9$ | $\le 10^5$ | $\le 5 \times 10^4$ | $=\max(0, 2n - 3)$ | $30$ | $!!$ 代表[双阶乘](https://baike.baidu.com/item/%E5%8F%8C%E9%98%B6%E4%B9%98/9500461)。