题目描述

贝西和其他牛需要在 $F(1\le F\le 5,000)$ 个牧场间移动（编号为 $1$ 到 $F$）。他们厌倦了走某些特定的路径，因而想要修建一些新路，使得在任意一对牧场之间总有至少两条路线可供选择。目前在每对牧场之间至少有一条路径。当然，他们只能在官方道路上移动。

当前有 $R(F-1\le R\le 10,000)$ 条道路，每条道路连接两个不同的牧场。请你确定必须修建的最小道路数量（每条新道路也要连接两个不同的牧场），使得在任意一对牧场之间至少有两条路线。两条路线只要没有使用同一条道路就被视为合法的（即使经过了相同的牧场）。

在同一对牧场之间可能已有多条路径。修建的新路可以与某条现有道路连接一对相同的牧场。

输入格式

第 $1$ 行：两个用空格分隔的整数：$F$ 和 $R$。

第 $2$ 行到第 $R+1$ 行：每行包含两个用空格分隔的整数，表示某条路径连接的两个牧场。

输出格式

一行一个整数，表示必须修建的新路径数量。

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

2

提示

样例解释：

初始路径如下：

可以在 $1$ 和 $6$ ， $4$ 和 $7$ 间修建新路。

一些例子：

• $1 - 2$：$1 \to2$ 或 $1 \to6 \to5 \to2$
• $1 - 4$：$1 \to2 \to3 \to4$ 或 $1 \to6 \to5 \to4$
• $3 - 7$：$3 \to4 \to7$ 或 $3 \to2 \to5 \to7$

可以发现，每对牧场之间都有至少两条路径。

其他道路修建方式也可能解决问题（例如从 $6$ 到 $7$ 的道路），但是添加两条是最少的。

（由 ChatGPT 4o 翻译并人工整改）