One state scattered on the islands of Oceania decided to create a network of roads (or rather, bridges). Each bridge can be navigated in both directions. A sequencing plan for the construction of bridges has been developed and it is known that after the construction of all the bridges it will be possible to drive over them from each island to each (perhaps through some intermediate islands
However, this moment may come before all the bridges are built. You need to determine such a minimum number of bridges, after the construction of which (in the order determined by the plan), it will be possible to get from any island to any other.
Input
The first line contains two numbers: the number of islands N (1≤N≤10000) and the number of bridges in the plan M (1≤M≤50000). Then there are M lines, each containing two numbers x and y (1≤x,y≤N) - the numbers of the cities that are connected by the next bridge in the plan.
Output
The program should output a single number - the minimum number of bridges built, after which it will be possible to get from any island to any other.
| Input |
Output |
|
4 5
1 2
1 3
2 3
3 4
4 1
|
4 |