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