P12902 [NERC 2020] Cactus Not Enough

在 NERC 2020 线上赛中竟然没有关于仙人掌的题目。这是个重大失误，因此裁判决定弥补这个遗憾。不解决一道关于仙人掌的问题，你就别想晋级 2021 年世界总决赛！ **仙人掌**是一种连通无向图，其中每条边最多属于一个简单环。直观地说，仙人掌是树的推广，允许存在某些环。仙人图中不允许出现多重边（一对顶点之间有多条边）或自环（顶点连接到自身的边）。 Cher 得到了一个仙人掌图。她称一个仙人掌图是**强**的，如果无法再添加任何一条边使其仍然保持仙人掌的性质。但 Cher 觉得她的仙人掌还不够强。她希望添加尽可能少的边使其变强，即创建一个具有相同顶点的新仙人掌图，使得原图是新图的子图，并且无法再添加任何一条边使其仍然保持仙人掌的性质。Cher 雇佣你来完成这个任务。所以…现在就看你的了！

输入包含一个或多个独立的测试用例。 每个测试用例的第一行包含两个整数 $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$）开头，后跟 $s_i$ 个 $1$ 到 $n$ 的整数。这些整数表示路径的顶点。路径中相邻的顶点是不同的。路径可以多次经过同一个顶点，但在整个测试用例中每条边恰好被遍历一次。图中没有多重边（任意两个顶点之间最多有一条边）。 输入的最后一行在所有测试用例之后总是包含两个零。它**不**定义任何测试用例，仅标记输入结束，不需要任何输出。 输入中的所有图都是仙人掌图。整个输入中所有 $n$ 的总和和所有 $m$ 的总和均不超过 $10^5$。

对于每个测试用例，首先输出一行，包含需要添加的最小边数 $A$。然后输出 $A$ 行，每行描述一条边为 $u_i$ $v_i$，其中 $u_i$ 和 $v_i$ 是要连接的顶点编号。添加这些边后，得到的图必须是一个强仙人掌图。

翻译由 DeepSeek V3 完成