DWITE
January 2012
Problem 3
Breaking Bonds

Brian is an expert organic chemist. He deals with compounds consisting of carbon atoms and bonds between them. He is given a compound that is connected: any two carbons are linked by some path of adjacent bonds. Notice that some carbons are connected by multiple bonds, and that they can form rings. With his incredible skills in organic synthesis, Brian is able to break one bond between any two carbons.

Brian would like to know how many ways he can choose one bond to break without disconnecting his compound. In this compound, allylbenzene, only the two marked bonds have this property. The carbons are numbered in some arbitrary way starting from 1, and the bonds are described by pairs of numbers.

The input file DATA3.txt will contain 5 test cases. Each test case will begin with 2 space-separated integers: C and B, the number of carbons and the number of bonds, respectively. Neither value will exceed 1000. B lines will follow, each containing 2 space-separated integers, describing the two ends of a bond.

The output file OUT3.txt will contain 5 lines of output, a single integer for each test case: the number of edges that, when broken, will disconnect the compound.

Sample Input (first 2 cases):
 
9 13
1 2
1 2
2 3
3 4
4 5
5 6
5 6
6 7
7 8
7 8
8 9
9 4
9 4
2 2
1 2
2 1
		        
Sample Output:
 
2
0