DWITE, January 2012, Problem 3

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 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 ~1\,000~. ~B~ lines will follow, each containing ~2~ space-separated integers, describing the two ends of a bond.

The output 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

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

Problem Resource: DWITE