CF2245G.NPC Challenge

This is an interactive problem.

There is a hidden undirected tree consisting of $n$ vertices. To find this tree, you may ask queries of the following form:

• Pick a sequence of distinct vertices $a_1, a_2, \ldots, a_k$, where $k \ge 1$.

The interactor will process your sequence and return a subset of these vertices, denoted by $S$. The set $S$ is generated by the following process:

• Initially, $S$ is an empty set.

• The interactor processes the vertices in the exact order they appear in your sequence, from $a_1$ to $a_k$.

• For each $a_i$, if $a_i$ does not share an edge with any vertex that is currently in $S$, then $a_i$ is added to $S$. Otherwise, $a_i$ is ignored.

• After processing all $k$ vertices, the interactor returns the final set $S$ to you. $S$ is represented by a binary string $s$ of length $k$, where $s_i=\texttt{1}$ if and only if $a_i \in S$.

Your task is to find all $n-1$ edges of the hidden tree. To make the problem harder, the sum of $k$ over all queries must not exceed $30 \cdot n$.

这是一个交互式问题。

存在一棵隐藏的、包含 $n$ 个顶点的无向树。为了找出这棵树，你可以提出如下形式的查询：

• 选取一个由互不相同的顶点组成的序列 $a_1, a_2, \ldots, a_k$，其中 $k \ge 1$。

交互器将处理你提供的序列，并返回该序列的一个子集 $S$。集合 $S$ 的生成过程如下：

• 初始时，$S$ 为空集。

• 交互器严格按照你在序列中给出的顺序（即从 $a_1$ 到 $a_k$）依次处理各顶点。

• 对每个 $a_i$，若 $a_i$ 与当前 $S$ 中任意顶点均无边相连，则将 $a_i$ 加入 $S$；否则忽略 $a_i$。

• 在处理完全部 $k$ 个顶点后，交互器将最终得到的集合 $S$ 返回给你。$S$ 以长度为 $k$ 的二进制字符串 $s$ 表示，其中当且仅当 $a_i \in S$ 时，$s_i = \texttt{1}$。

你的任务是找出隐藏树的全部 $n-1$ 条边。为增加难度，所有查询中 $k$ 值的总和不得超过 $30 \cdot n$。

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

The first line of each test case contains an integer $n$ ($2 \le n \le 10^3$), representing the number of vertices in the hidden tree.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^3$.

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

每个测试用例的第一行包含一个整数 $n$（$2 \le n \le 10^3$），表示隐藏树中的顶点数量。

保证所有测试用例的 $n$ 值之和不超过 $10^3$。

null

In the first test case, the hidden tree consists of $n=2$ vertices, and the only edge is $(1,2)$.

• For the first query, $a=[1,2]$:

  • Vertex $1$ is processed. Currently, $S$ is empty. Since $1$ has no neighbors in $S$, it is added to $S$. $S$ becomes ${1}$.

  • Vertex $2$ is processed. Its neighbor, vertex $1$, is already in $S$. Thus, vertex $2$ is ignored.

In the second test case, the hidden tree consists of $n=5$ vertices. The edges are $(1, 2)$, $(2, 3)$, $(2, 4)$, and $(3, 5)$.

• For the first query, $a=[1,2,5]$:

  • Vertex $1$ is processed. $S$ is empty. It is added to $S$. $S$ becomes ${1}$.

  • Vertex $2$ is processed. It shares an edge with vertex $1 \in S$. It is ignored.

  • Vertex $5$ is processed. Its only neighbor is vertex $3 \notin S$. It is added to $S$. $S$ becomes ${1, 5}$.

• For the second query, $a=[5,3,4,2,1]$:

  • Vertex $5$ is processed. $S$ is empty. It is added to $S$. $S$ becomes ${5}$.

  • Vertex $3$ is processed. It shares an edge with vertex $5 \in S$. It is ignored.

  • Vertex $4$ is processed. Its only neighbor is vertex $2 \notin S$. It is added to $S$. $S$ becomes ${4, 5}$.

  • Vertex $2$ is processed. It shares an edge with vertex $4 \in S$. It is ignored.

  • Vertex $1$ is processed. Its only neighbor is vertex $2 \notin S$. Since it has no neighbors in $S$, it is added to $S$.

在第一个测试用例中，隐藏的树包含 $n=2$ 个顶点，且唯一的一条边为 $(1,2)$。

• 对于第一次查询，$a=[1,2]$：

  • 处理顶点 $1$。此时 $S$ 为空。由于 $1$ 在 $S$ 中没有邻居，因此将其加入 $S$。$S$ 变为 $\{1\}$。

  • 处理顶点 $2$。其邻居顶点 $1$ 已在 $S$ 中。因此忽略顶点 $2$。

在第二个测试用例中，隐藏的树包含 $n=5$ 个顶点。边集为 $(1, 2)$、$(2, 3)$、$(2, 4)$ 和 $(3, 5)$。

• 对于第一次查询，$a=[1,2,5]$：

  • 处理顶点 $1$。$S$ 为空。将其加入 $S$。$S$ 变为 $\{1\}$。

  • 处理顶点 $2$。它与 $S$ 中的顶点 $1$ 相邻。因此忽略顶点 $2$。

  • 处理顶点 $5$。它的唯一邻居是顶点 $3$，而 $3 \notin S$。因此将其加入 $S$。$S$ 变为 $\{1, 5\}$。

• 对于第二次查询，$a=[5,3,4,2,1]$：

  • 处理顶点 $5$。$S$ 为空。将其加入 $S$。$S$ 变为 $\{5\}$。

  • 处理顶点 $3$。它与 $S$ 中的顶点 $5$ 相邻。因此忽略顶点 $3$。

  • 处理顶点 $4$。它的唯一邻居是顶点 $2$，而 $2 \notin S$。因此将其加入 $S$。$S$ 变为 $\{4, 5\}$。

  • 处理顶点 $2$。它与 $S$ 中的顶点 $4$ 相邻。因此忽略顶点 $2$。

  • 处理顶点 $1$。它的唯一邻居是顶点 $2$，而 $2 \notin S$。由于它在 $S$ 中没有邻居，因此将其加入 $S$。