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 to disconnect 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 two 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 two space-separated integers (each between 1 and C), describing the two carbon ends of a bond.
The output file OUT3.txt will contain 5 lines of output, each being a single integer for the test case, which the number of edges such that removing that single edge will disconnect the compound.
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
2
0