#1968. [USACO06JAN] Redundant Paths G

[USACO06JAN] Redundant Paths G

题目描述

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

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

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

输入格式

第 11 行:两个用空格分隔的整数:FF 和 RR。

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

输出格式

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

样例

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

题目来源:洛谷 P2860