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$ 的值！

无

第一个测试用例对应的图如下。  在该图中，共有 $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 翻译