CF2150F.Cycle Closing

Kubbi - The Cairn

⠀

给定一个无向连通图 $G$，包含 $n$ 个节点和 $m$ 条边。图中不存在自环和重边。

每次操作，你需要按如下顺序进行：

• 选择一个正整数 $k$（$1 \le k \le n$）；
• 选择一个整数 $s$（$0 \le s \le \frac{n \cdot (n - 1)}{2}$）；
• 输出 $s$ 条长度为 $k-1$ 的简单路径（$v_{i,1} \leftrightarrow v_{i,2} \leftrightarrow \ldots \leftrightarrow v_{i,k}$）；
• 对于每个 $i = 1$ 到 $s$，在图中加入一条新边 $(v_{i,1}, v_{i,k})$。

注意，操作中新加的边只能在之后的操作中使用，因为是等所有路径都输出后才添加这些边。

请在至多 $2$ 次操作内，使图 $G$ 变为完全图。即，图中每对 $u < v$ 的节点 $(u, v)$ 都恰好有一条边。

注意：本题提供了前 $10$ 个测试点的输入文件和 $2$ 个检查器（C++ 和 Python 版本），用于校验你的输出。你可以在比赛资料包中下载这些文件。

每个测试包含多个测试用例。第一行为测试用例数 $t$（$1 \le t \le 10^3$）。接下来是各个测试用例。

每个测试用例第一行包含两个整数 $n$ 和 $m$（$3 \leq n \leq 200$，$n - 1\leq m \leq \frac{n(n-1)}{2}$），表示图中节点数和边数。

接下来 $m$ 行，每行两个整数 $u_i$，$v_i$（$1 \leq u_i, v_i \leq n$，$u_i \neq v_i$），表示一条边 $(u_i, v_i)$。图保证连通，且不存在自环和重边。

保证所有测试用例中 $\sum n^2 \leq 4 \cdot 10^4$。

对于每个测试用例，输出如下内容。

第一行，输出操作次数 $op$（$0 \le op \le 2$）。对每次操作：

• 第一行输出本次操作选择的 $k$（$1 \le k \le n$）；
• 第二行输出简单路径数 $s$（$0 \le s \le \frac{n \cdot (n - 1)}{2}$）；
• 接下来 $s$ 行，每行 $k$ 个正整数，表示一条简单路径 $v_{i,1} \leftrightarrow v_{i,2} \leftrightarrow \ldots \leftrightarrow v_{i,k}$。

以下是第一个测试用例的解释：

输出内容	说明
$\texttt{2}$	要进行的操作次数（$=2$）。
$\texttt{3}$	第一次操作，选择 $k=3$（路径长度为 $2$）。
$\texttt{1}$	本次操作输出 $s=1$ 条简单路径。
$\texttt{2 1 3}$	该路径为 $2\to1\to3$，操作结束后将加入边 $(2,3)$。
$\texttt{4}$	第二次操作，选择 $k=4$（路径长度为 $3$）。
$\texttt{2}$	本次操作输出 $s=2$ 条简单路径。
$\texttt{4 1 2 3}$	第一条路径，操作结束后加入边 $(3,4)$。
$\texttt{4 1 3 2}$	第二条路径，操作结束后加入边 $(2,4)$。
	注意不能输出 $\texttt{4 3 1 2}$，因 $(3,4)$ 这条新加的边只有在本次操作全部结束后才会存在。

由 ChatGPT 5 翻译