Competitions

DSU

In Ukraine, as you know, a lot of problems. One of them - the road. The newly elected president of Ukraine decided to do road construction. His goal - to build some additional amount of roads between cities so that you can drive from any city of Ukraine in any (possibly through other cities, not necessarily directly). Naturally, any additional roads should be built as possible.

We assume that all the roads in Ukraine bilateral (and already available, and those that will be built), that is, it may move in both directions. Note that between the two cities may be somewhat expensive. In addition, there may be roads connecting the city to itself.

Input

The first line contains two natural numbers n and m (1n, m10000) - number of cities and the number of existing roads. The following m lines contain two integers ai and bi (1ai, bin) - the numbers of cities connected to an existing road.

Output

Print the minimum number of roads to be constructed, to exist a path from any city to any.

Time limit 1 second
Memory limit 128 MiB
Input example #1
7 5
1 3
2 3
3 2
2 4
6 7
Output example #1
2

Source Crimea-2010