URI Online Judge | 1790

Detecting Bridges

By Marcos Castro, Universidade Federal de São Paulo BR Brazil

Timelimit: 1

Pedrinho Ritchie lives in a country called Graphland. The cities of this country are interconnected by bridges. There are not isolated cities and no bridge inserted more than once. His teacher suggested a challenge: detect the number of the bridges which are not contained in any cycle. We can say that a cycle starts and ends at the same city and no city is repeated.

Pedrinho likes very much of programming challenges, but needs your help to solve this problem, do you can help?


The input ends with EOF. For each test case, the first line contains two positive integers C and P that represent respectively the amount of cities (2 <= C <= 50) and the amount of bridges (1 <= P <= 1250). Following are the lines where each line contains two integers positives X and Y (indexed from 1) indicating that there is a bridge linking the cities X and Y.


Your program should print the number of bridges that are not contained in any cycle.

Input Sample Output Sample

4 3

1 2

2 3

3 4