3443 - [USACO06JAN] Redundant Paths G

题目描述

为了从 F(1≤F≤5,000) 个牧场(编号为 1 到 F)中的一个到达另一个牧场,贝西和其他牛群被迫经过腐烂苹果树附近。奶牛们厌倦了经常被迫走特定的路径,想要修建一些新路径,以便在任意一对牧场之间总是有至少两条独立的路线可供选择。目前在每对牧场之间至少有一条路径,他们希望至少有两条。当然,他们只能在官方路径上从一个牧场移动到另一个牧场。

给定当前 R(F−1≤R≤10,000) 条路径的描述,每条路径恰好连接两个不同的牧场,确定必须修建的最少新路径数量(每条新路径也恰好连接两个牧场),以便在任意一对牧场之间至少有两条独立的路线。若两条路线不使用相同的路径,即使它们沿途访问相同的中间牧场,也被视为独立的。

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

输入

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

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

输出

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

样例

输入

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

输出

2
题目参数
时间限制 1 秒
内存限制 128 MB
提交次数 1
通过人数 1
金币数量 4 枚
难度 提高


上一题 下一题