CF1510C.Cactus Not Enough

省选/NOI-

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

在 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$ ，表示需要连接的顶点编号。添加这些边后，所得图必须是强仙人掌。

输入输出样例

输入#1

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

说明/提示

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页