← 返回题目列表

Codeforces · 2150/F

F. 循环关闭

中文机器翻译题面 查看原题
库比 - 凯恩
⠀

给您一个无向连通图 $$$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})$$$。

请注意,由某些操作添加的边只能由以后的操作使用,因为这些边是在打印所有简单路径的末尾添加的。

使 $$$G$$$ 最多完成 $$$2$$$ 操作。具体来说,$$$G$$$ 必须包含每条边 $$$(u, v)$$$ 且 $$$u \lt v$$$ 恰好一次。

注意: 我们为您提供了此问题的第一个 $$$10$$$ 测试的输入文件,以及用于验证输出的 $$$2$$$ 检查器(一个在 C++ 中,一个在 Python 中)。检查器假设您遵循问题的输入和输出格式。您可以从竞赛材料部分下载 zip 文件。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^3$$$)。测试用例的描述如下。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$3 \leq n \leq 200$$$, $$$n - 1\leq m \leq n(n-1)/2$$$) - 分别是 $$$G$$$ 中的节点数和边数。

接下来的 $$$m$$$ 行包含两个整数 $$$u_i$$$、$$$v_i$$$ ($$$1 \leq u_i, v_i \leq n$$$, $$$u_i \neq v_i$$$),表示边 $$$(u_i, v_i)$$$。该图是连通的,不包含自环,也不包含多重边。

保证所有测试用例的 $$$n^2$$$ 总和不超过 $$$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}$$$。

示例

输入
复制

3
4 3
1 2
1 3
1 4
3 3
1 2
1 3
2 3
5 4
4 2
2 3
3 5
5 1

输出
复制

2
3
1
2 1 3
4
2
4 1 2 3
4 1 3 2
0
2
4
2
4 2 3 5
2 3 5 1
3
4
4 5 1
4 5 3
2 1 5
3 2 1

注意

这是第一个测试用例的解释:

输出令牌说明
$$$\texttt{2}$$$要执行的操作数 ($$$=2$$$)。
$$$\texttt{3}$$$操作1。  $$$k$$$ 的值($$$k=3$$$,路径长度为 $$$2$$$)。
$$$\texttt{1}$$$此操作中简单路径的数量 $$$s$$$ ($$$s=1$$$)。
$$$\texttt{2 1 3}$$$打印的唯一简单路径;当操作结束时,它会添加快捷边 $$$(2,3)$$$。
$$$\texttt{4}$$$操作2。  $$$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)$$$,直到它不存在 之后 此操作的两条路径均已处理。