Safety Grade#2561
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. The network is considered connected if any two sites are directly or indirectly connected; otherwise, the network is disconnected. The safety grade of the network is defined as follows:
is if the network is disconnected, or if the number of sites is or .
If the number of sites is greater than , then is the minimum number of cables whose removal disconnects the network. That is, removing any S-1 cables keeps the network connected, but there exist cables whose removal disconnects the network.
For example, consider the network in Figure , where the sites correspond to the shaded circles and the cables are indicated by lines. The network remains connected when any single cable is removed, but removing the cables and disconnects the network. Another way to disconnect the network is to remove the cables and . The safety grade is S = 2.
Write a program that reads several data sets from a text file and computes the safety grade of the cable networks encoded in these data sets.
Each data set starts with two integers: the number of sites 0 \le n \le 100 and the number of cables 0 \le m \le 1000 in the network. Then follow data pairs , where u < v, and and are site identifiers (integers from to n-1). A pair designates a cable that interconnects the sites and . The pairs may occur in any order. With the exception of the pairs , which do not contain white space, white space may occur freely in the input. Input data is terminated by the end of file and is correct.
For each data set, the program prints, starting at the beginning of a line, the safety grade of the encoded network to the standard output.
Example 1