Problem1541--VIJOS-P1325

1541: VIJOS-P1325

Time Limit: 0 Sec  Memory Limit: 128 MB
Submit: 0  Solved: 0
[Submit] [Status] [Web Board] [Creator:]

Description

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

Input

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

Output

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

Sample Input Copy

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

Sample Output Copy

3
2

HINT

      1      2      3       +---+---+                  |      |               |      |   6  +---+---+  4             /  5           /          /    7  + 上图是样例所表示的一个图。 下图是改变后的图,其中虚线表示应连接的边。       1      2      3       +---+---+          :      |      |       :      |      |   6  +---+---+  4             /  5    :           /          :         /            :   7  +  -  -  -  -