← 返回题目列表

Codeforces · 1510/C

C. 仙人掌不够

中文机器翻译题面 查看原题

NERC 2020 在线回合中仙人掌没有问题。这是一个严重的错误,所以法官决定纠正它。如果不解决仙人掌问题,您将无法进入 2021 年世界总决赛!

A 仙人掌 是一个连通的无向图,其中每条边最多位于一个简单循环上。直观上,仙人掌是允许存在某些循环的树的概括。仙人掌中不允许存在多重边(一对顶点之间的多条边)和循环(将顶点连接到自身的边)。

雪儿有一棵仙人掌。她称仙人掌 强 如果不可能为其添加边缘以使其仍然是仙人掌。但雪儿认为她的仙人掌不够坚固。她想为其添加尽可能少的边数以使其坚固,即。 e. 创建一个具有相同顶点的新仙人掌,以便原始仙人掌是新仙人掌的子图,并且不可能向其添加另一条边以使图仍然是仙人掌。雪儿雇用你为她做这项工作。所以……就看你了!

输入

输入由一个或多个独立的测试用例组成。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n \le 10^5$$$, $$$0 \le m \le 10^5$$$),其中 $$$n$$$ 是图中的顶点数。顶点编号从 $$$1$$$ 到 $$$n$$$。图的边由一组边不同的路径表示,其中 $$$m$$$ 是此类路径的数量。

以下每条 $$$m$$$ 行都包含图中的一条路径。路径以整数 $$$s_i$$$ ($$$2 \le s_i \le 1000$$$) 开头,后跟从 $$$1$$$ 到 $$$n$$$ 的 $$$s_i$$$ 整数。这些 $$$s_i$$$ 整数表示路径的顶点。路径中的相邻顶点是不同的。该路径可以多次经过同一顶点,但在整个测试用例中每条边都只经过一次。图中不存在多重边(任意两个顶点之间最多有一条边)。

所有测试用例之后输入的最后一行始终包含两个零。确实如此 不 定义一个测试用例。它只是标记输入的结束,不需要任何输出。

输入中的所有图形都是仙人掌。输入中 $$$n$$$ 的所有值的总和以及 $$$m$$$ 的所有值的总和均不超过 $$$10^5$$$。

输出

对于每个测试用例,首先输出具有尽可能少的附加边 $$$A$$$ 的行。然后输出 $$$A$$$ 行,每行将一条边描述为 $$$u_i$$$ $$$v_i$$$,其中 $$$u_i$$$ 和 $$$v_i$$$ 是要连接的顶点数。添加这些边之后,得到的图一定是一个强仙人掌。

示例

输入
复制

6 1
7 1 2 5 6 2 3 4
3 1
4 1 2 3 1
5 2
3 1 3 5
3 1 2 4
7 2
6 1 2 3 4 5 3
3 6 5 7
0 0

输出
复制

1
1 4
0
1
5 4
2
1 3
6 7