G :: Safety Grade
Time Limit: 10 Seconds Memory Limit: 65536 KB
The sites of a cable network are interconnected by cables such that a cable connects a single pair of distinct sites, and a pair of sites can be connected by several cables. We say that the network is connected if any two sites in the network are directly or indirectly connected; otherwise the network is disconnected. The safety grade S of the network is defined as follows.
S is 0 if the network is disconnected, or the number of sites is 0 or 1.
If the number of sites is greater than 1 then S is the minimum number of cables that disconnect the network when removed, i.e. removing any S-1 cables keeps the net connected, while the removal of some S cables disconnects the net.
For example, consider the net in figure 1, where the sites correspond to the shadowed circles and the cables are indicated by lines. The network stays connected when removing any single cable, whereas the removal of cables (0,2), and (1,3) disconnects the net. Another variant for disconnecting the net is by removing the cables (2,4) and (2,4). The safety grade is S=2.
Input
Write a program that reads several data sets from a text file and computes the safety grade of the cable networks the data sets encode. Each data set starts with two integers: the number 0 ≤ n ≤ 100 of sites in the net, and 0≤m≤1000 the number of cables in the net. Follow m data pairs (u,v), u<v, where u and v are site identifiers (integers from 0 to n-1). A pair (u,v) designates a cable that interconnects the sites u and v. The pairs may occur in any order. Except the (u,v) pairs, which do not contain white spaces, white spaces can occur freely in input. Input data terminate with an end of file and are correct.
Output
For each data set, the program prints on the standard output, from the beginning of a line, the safety grade of the encoded net.
Sample Input
0 0 2 1 (0,1) 2 0 5 8 (0,1) (1,3) (2,3) (0,2) (0,1) (2,3) (2,4) (2,4)
Sample Output
0 1 0 2Submit
Source: South Eastern European Regional Contest 2011