#5770. 「CEOI2026」剪花

标签: 传统 | 时间限制: 4000 ms | 内存限制: 256 MiB |

题目描述

题目译自 CEOI 2026 Day2 T1「Flower Cutting」

在 CEOI 社区花园里，我们种植了一群特殊的鲜花，它们的根紧紧地缠绕纠结在一起。若我们将根剪断，只要剪得不过于激进以至于造成不可逆的损伤，它们就能够重新生长恢复。

若两朵花 $a$ 和 $b$ 的根缠绕在一起，我们称它们是连通的；否则，称它们是未连通的。根按照以下规则生长：假设 $a$ 和 $b$ 是两朵未连通的花。若存在至少 $2$ 朵其他的花 $c$ 和 $d$，使得 $a$ 和 $b$ 都同时与 $c$ 和 $d$ 连通，则 $a$ 和 $b$ 之间的根就会生长，它们之间会变得连通。

这些鲜花已经生长了一段时间，所有能够根据上述规则长出的根都已经长成了。换句话说，若存在某些花 $c$ 和 $d$ 同时与两朵花 $a$ 和 $b$ 连通，则 $a$ 和 $b$ 之间保证已经是连通的。

我们需要将这个花园连根拔起并迁移到下一个 CEOI 举办地。为了简化搬迁，我们希望尽可能多地剪断花根。然而，我们希望鲜花随后能够重新生长恢复到当前的状态。在保证它们仍然能够重新生长恢复到当前状态的前提下，我们最多可以剪断多少对连通鲜花之间的根？生长过程需要经历多少轮迭代并不重要。

输入格式

第一行包含两个用空格分隔的整数 $n$ 和 $m$，分别表示花的数量以及它们之间现有的连通关系数量。

接下来 $m$ 行，每行包含一对整数 $a_i$ 和 $b_i$，表示花 $a_i$ 与花 $b_i$ 之间是连通的。花用整数 $1 \ldots n$ 进行编号。输入保证符合题目描述中所述的生长规则。

输出格式

输出一个整数，表示我们最多可以剪断的连通关系数量。

样例

输入

9 14
1 2
1 4
1 5
2 4
2 5
3 4
4 5
3 6
4 6
6 7
6 9
7 9
8 9
5 8

输出

2

样例中的鲜花在进行任何剪切之前的状态。可以验证，根据所述的生长规则，无法再长出额外的连通关系。

剪切后的样例鲜花少掉了 $2$ 条连通关系。$1$ 和 $2$ 之间的连通关系可以重新长出，因为花 $1$ 和花 $2$ 都同时与花 $4$ 和花 $5$ 连通。类似地，$4$ 和 $5$ 之间的连通关系也可以重新长出，因为花 $4$ 和花 $5$ 都同时与花 $1$ 和花 $2$ 连通。

数据范围与提示

对于所有输入数据，满足：

• $1 \leq n \leq 1000$
• $1 \leq m \leq 10^5$

详细子任务附加限制及分值如下表所示。