Safety Grade

Time limit1sMemory limit128 MB

Summary

Given multigraphs with repeated edges, compute the global minimum edge cut (edge connectivity) or 0 if disconnected or trivial.

Level: Medium6 of 10
Topics: Graph, Math
Solved: No attempts yet

Problem

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; that is, removing any $S-1$ cables keeps the network connected, while the removal of some $S$ cables disconnects it.

For example, consider a network on sites $0, \dots, 4$ whose cables are $(0,1)$ (twice), $(1,3)$ , $(2,3)$ (twice), $(0,2)$ and $(2,4)$ (twice). The network stays connected when any single cable is removed, whereas removing cables $(0,2)$ and $(1,3)$ disconnects it; another way to disconnect it is to remove both copies of cable $(2,4)$ . Its safety grade is $S = 2$ .

Write a program that reads several data sets and computes the safety grade of the cable networks the data sets encode.

Input

Each data set starts with two integers: the number $0 \le n \le 100$ of sites in the network, and the number $0 \le m \le 1000$ of cables. Then follow $m$ data pairs $(u, v)$ , with $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 for the $(u, v)$ pairs, which do not contain white spaces, white spaces can occur freely in the input. The input terminates at end of file and is always correct.

Output

For each data set, print, from the beginning of a line, the safety grade of the encoded network.

Note

In the sample, the first data set encodes an empty network, the second a network with 2 sites and 1 cable, the third a disconnected network with two sites, and the fourth the five-site network described above.

Examples5

Example 1

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)

Expected output

Example 2
Input
```
3 3 (0,1) (1,2) (0,2)
```
Expected output
```
2
```
Example 3
Input
```
3 2 (0,1) (1,2)
```
Expected output
```
1
```
Example 4
Input
```
1 0
```
Expected output
```
0
```
Example 5
Input
```
0 0
```
Expected output
```
0
```