CF2196C2.Interactive Graph (Hard Version)

This is the hard version of the problem. The difference between the versions is that in this version, you can ask no more than $n + m$ questions, and $n \leq 30$. You can hack only if you solved all versions of this problem.

This is an interactive problem.

The jury has thought of a directed acyclic graph without loops and multiple edges, which has $n$ vertices and $m$ edges.

Your task is to determine which edges are in this graph. To do this, you can ask questions of the form: what does the $k$-th path look like in the lexicographically$^{\text{∗}}$ sorted list of all paths in the graph.

A path in the graph is a sequence of vertices $u_{1}, u_{2}, \dots, u_{l}$, such that for any $i \lt l$, there exists an edge ($u_{i}, u_{i + 1}$) in the graph.

Your task is to accomplish this by asking no more than $n + m$ questions.

$^{\text{∗}}$A sequence $a$ is lexicographically smaller than a sequence $b$ if and only if one of the following holds:

• $a$ is a prefix of $b$, but $a \ne b$; or
• in the first position where $a$ and $b$ differ, the sequence $a$ has a smaller element than the corresponding element in $b$.

这是该问题的困难版本。两个版本的区别在于，在本版本中，你最多只能提出 $n + m$ 个问题，且满足 $n \leq 30$。仅当你已解决该问题的所有版本时，才可进行 Hack。

这是一个交互式问题。

出题人构思了一个不含自环和重边的有向无环图（DAG），该图具有 $n$ 个顶点和 $m$ 条边。

你的任务是确定该图中具体包含哪些边。为此，你可以提出如下形式的问题：图中所有路径按字典序$^{\text{∗}}$排序后，第 $k$ 条路径是什么？

图中的一条路径是指一个顶点序列 $u_{1}, u_{2}, \dots, u_{l}$，使得对任意 $i \lt l$，图中均存在一条从 $u_i$ 指向 $u_{i+1}$ 的边。

你需要在至多 $n + m$ 次提问内完成该任务。

$^{\text{∗}}$ 序列 $a$ 字典序小于序列 $b$，当且仅当满足以下条件之一：

• $a$ 是 $b$ 的真前缀（即 $a$ 是 $b$ 的前缀，但 $a \ne b$）；或
• 在 $a$ 与 $b$ 首次出现不同元素的位置上，$a$ 中对应位置的元素小于 $b$ 中对应位置的元素。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10$). The description of the test cases follows.

Each test case consists of a single line with an integer $n$ ($1 \le n \le 30$) — the number of vertices in the graph.

The jury guarantees that the given graph does not contain cycles or multiple edges.

Note that $m$ is unknown to you!

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

每个测试用例由一行组成，其中包含一个整数 $n$（$1 \le n \le 30$）——表示图中顶点的数量。

评测组保证所给图不含环或重边。

注意：$m$ 对你而言是未知的！

The graph for the first test case.

In this graph, there are $15$ paths, which are arranged in lexicographic order as follows:

• $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$

第一个测试用例的图。

在该图中，共有 $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$