CF2196C2 Interactive Graph (Hard Version)

这是该问题的难度较高的版本。不同之处在于，在本版本中，你最多只能询问 $n+m$ 个问题，并且 $n \leq 30$。只有在你解决了该问题的所有版本后，才可以对其进行 Hack。 这是一个交互式问题。 命题人想出了一个没有环和重边的有向无环图（DAG），该图有 $n$ 个点和 $m$ 条边。 你的任务是确定图中具体有哪些边。为此，你可以提出形式为：“图中所有路径按字典序排序后的第 $k$ 条路径长什么样？”的问题。 图中的一条路径指的是一组顶点序列 $u_{1}, u_{2}, \dots, u_{l}$，使得对于任意 $i < l$，图中存在一条有向边 $(u_{i}, u_{i+1})$。 你需要通过不超过 $n+m$ 次的提问来完成任务。 $^{\ast}$ 序列 $a$ 在字典序上小于序列 $b$ 当且仅当满足下列之一： - $a$ 是 $b$ 的前缀，且 $a \ne b$； - 在 $a$ 和 $b$ 的第一个不同位置，$a$ 的对应元素小于 $b$ 的对应元素。

每个测试包含多组数据。第一行包含一个整数 $t$（$1 \le t \le 10$），表示测试用例的数量。每个测试用例包含一行，包含一个整数 $n$（$1 \le n \le 30$），表示图中的顶点数。 保证所给的图中不包含环和重边。 注意，你并不知道 $m$ 的值！

无

**交互格式** 每个测试用例的交互，首先读入一个整数 $n$。 随后你最多可以提出 $n + m$ 个询问。 要提问，就输出一行格式为 `? k` 的字符串（不含引号），其中 $1 \leq k \leq 2^{30}$。每次提问后，读入一个整数 $q$ —— 第 $k$ 条路径上的顶点数。若 $q = 0$，则这条路径不存在；否则读入 $q$ 个整数 —— 构成该路径的顶点编号。 要报告答案，先输出一行格式为 `! m` 的字符串，接着输出 m 行，每行按 `u v` 的格式描述一条边，表示存在一条从 u 指向 v 的边。边的输出顺序任意。输出答案不计入询问次数。 可以证明，在给定约束下，图中不同路径的数量不超过 $2^{30}$。 每次打印询问之后，别忘了输出换行并**刷新**输出，否则你会得到 Idleness limit exceeded（空闲超限）。 如果在交互的任意一步，你读到的是 $−1$ 而不是有效数据，你的程序必须立即退出。这意味着你的解法会因为非法询问或其它错误而得到 Wrong answer（判错）。若没有退出，程序会继续从已关闭的流中读取，可能导致任意（无法预期的）判定结果。 ∗ 刷新输出可使用： - C++ 中：`fflush(stdout)` 或 `cout.flush()` - Python 中：`sys.stdout.flush()` - 其他语言见相应文档。 **样例解释** 第一个测试用例对应的图如下。  在该图中，共有 $15$ 条路径，按字典序排序如下： - $1$ - $1 \to 2$ - $1 \to 2 \to 4$ - $1 \to 2 \to 5$ - $1 \to 3$ - $1 \to 3 \to 4$ - $1 \to 3 \to 5$ - $2$ - $2 \to 4$ - $2 \to 5$ - $3$ - $3 \to 4$ - $3 \to 5$ - $4$ - $5$ 由 ChatGPT 5 翻译