天堂岛

Grade 100 Open Time Wednesday, 17 June 2020, 10:00 PM
Discount 0.8 Time Discount Wednesday, 17 June 2020, 10:00 PM
Allow late Yes Close Time Wednesday, 17 June 2020, 10:00 PM
Input file island.in Output file island.out

【题目描述】5.36 天堂岛(island)POJ 3352

在海上建立的人工岛屿被一家跨国企业收购并开发成了旅游景点,最大的一座岛上有N个旅游景点,任意2个旅游景点之间有路径连通(注意不一定是直接连通)。而为了给游客提供更方便的服务,该企业要求道路部门在某些道路增加一些设施。

道路部门每次只会选择一条道路施工,在该条道路施工完毕前,其他道路依然可以通行。然而有道路部门正在施工的道路,在施工完毕前是禁止游客通行的,这就导致了在施工期间游客可能无法到达一些景点。

为了在施工期间所有旅游景点依然能够正常对游客开放,该企业决定搭建一些临时桥梁,使得不管道路部门选在哪条路进行施工,游客都能够到达所有旅游景点。给出当下允许通行的r条道路,问该企业至少再搭建几条临时桥梁,才能使得游客无视道路施工到达所有旅游景点?

【输入格式】

第一行两个整数n(3≤n≤1 000)和 r(2≤r≤1 000),表示景点数和路径数。景点从1到n编号,随后r行包含两个整数v 和 w,表示v和w之间有条路,保证无重边。

【输出格式】

输出最小再搭建几条临时桥梁。

【输入样例1】

10 12

1 2

1 3

1 4

2 5

2 6

5 6

3 7

3 8

7 8

4 9

4 10

9 10

【输出样例1】

2

【输入样例2】

3 3

1 2

2 3

1 3

【输出样例2】

0