CF1510C Cactus Not Enough

在 NERC 2020 线上赛中没有出现关于仙人掌（cactus）的题目。这是一个严重的失误，因此评委们决定修正这个问题。你必须解决一道关于仙人掌的题目，才能晋级 2021 年世界总决赛！ 仙人掌是一种连通的无向图，其中每条边至多属于一个简单环。直观上，仙人掌是树的推广，允许存在一些环。仙人掌中不允许存在重边（即一对顶点之间有多条边）和自环（即一条边连接同一个顶点）。 Cher 拥有一棵仙人掌。她称仙人掌是“强仙人掌”，当且仅当无法再向其中添加一条边使其仍然是仙人掌。但 Cher 认为她的仙人掌还不够强。她希望添加尽可能少的边，使其变为强仙人掌。也就是说，构造一个新的仙人掌，顶点集不变，原仙人掌是新仙人掌的子图，并且无法再向新仙人掌添加一条边使其仍然是仙人掌。Cher 雇佣了你来完成这项工作。现在，这个任务就交给你了！

输入包含一个或多个独立的测试用例。 每个测试用例的第一行包含两个整数 $n$ 和 $m$（$1 \le n \le 10^5$，$0 \le m \le 10^5$），表示图中顶点的数量。顶点编号为 $1$ 到 $n$。图中的边由一组互不重叠的路径表示，$m$ 表示路径的数量。 接下来的 $m$ 行，每行描述一条路径。每条路径以一个整数 $s_i$（$2 \le s_i \le 1000$）开头，后跟 $s_i$ 个 $1$ 到 $n$ 之间的整数，表示路径经过的顶点。路径中相邻的顶点各不相同。路径可以多次经过同一个顶点，但在整个测试用例中，每条边只出现一次。图中不存在重边（任意两点之间至多有一条边）。 所有输入的图都是仙人掌。所有测试用例的 $n$ 之和不超过 $10^5$，所有 $m$ 之和也不超过 $10^5$。 所有测试用例输入结束后，最后一行包含两个零，表示输入结束，不需要输出。

对于每个测试用例，首先输出一行，包含需要添加的最少边数 $A$。接下来输出 $A$ 行，每行两个整数 $u_i$ $v_i$，表示需要连接的顶点编号。添加这些边后，所得图必须是强仙人掌。

由 ChatGPT 4.1 翻译