#499. 徐老师的道路规划
徐老师的道路规划
说明
徐老师的王国有若干城市,城市之间有若干道路,道路都是双向的,城市间互相均可直接或间接到达,但是有些城市之间可能只有一条路径,这样会导致某些时刻交通拥堵。徐老师希望再建设若干条道路,使得对于任意两个城市,都可以有至少两条独立的路径连接,独立路径指与其它路径没有公共边。不过徐老师觉得件太多的新道路没什么意义,所以他想知道至少还需要建设多少条道路才可以满足他的需求。输入格式
第一行两个正整数 N,M,分别表示一共有 N 个城市,M 条道路(3<= N<= 10^4,1<= M<= 2 \times 10^4)。接下来 M 行,每行两个不相等的整数 u 和 v,表示城市 u 和城市 v 之间有一条道路 (1<= A,B <= N)。
数据保证图连通且没有自环和重边。
输出格式
一行,包含一个整数,表示徐老师至少要新建的道路数。样例
3 2
1 2
2 3
1