问题1378--桐桐的糖果计划

1378: 桐桐的糖果计划

时间限制: 1 Sec  内存限制: 128 MB
提交: 72  解决: 30
[提交] [状态] [讨论版] [命题人:]

题目描述

桐桐很喜欢吃棒棒糖。他家处在一大堆糖果店的附近。 但是,他们家的区域经常出现塞车、塞人等情况,这导致他不得不等到塞的车或人走光了他才能去买到他最爱吃的棒棒糖品种。于是,他去找市长帮他修路,使得每两个糖果店之间至少有两条完全不同的路。可是市长经费有限,于是让桐桐找出哪些路被塞住后会使某些糖果店与糖果店间无法到达及最少的修路条数。你能帮助他吃到他最喜爱的糖果吗? 注:1-> 3-> 2    和  1-> 3-> 4-> 2  为不完全不同的路,即不符合题意的路。         1-> 3-> 4-> 2  和  1-> 5-> 2  为完全不同的路,即符合题意的路。

输入

输入第一行是两个数n,m(n< =5000,m< =10000) 接下来的m行,每行两个数i,j,表示i,j间有一条边连接。

输出

输出有两行。第一行为塞住后就不可以到达某些糖果店的道路条数,第二行为最少的修路条数。

样例输入 Copy

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

样例输出 Copy

3
2

来源/分类