Minimum Gifts Distribution

In a country, there are N regions and M bidirectional roads connecting them. The government wants to ensure that every region receives at least one gift. However, due to the road network, gifts can only be delivered across the roads. Under the assumption that the cost can be minimized by sending gifts only along the necessary roads, you are required to determine the minimum number of gifts that must be dispatched.

In a connected network, distributing gifts along the minimum spanning tree ensures that every region is connected. Since a spanning tree of a connected graph with N nodes has exactly $$N-1$$ edges, the minimum number of gifts required is $$N-1$$. Note that if there is only one region, no gift is needed.

inputFormat

The input is given via stdin and consists of:

• The first line contains two integers N and M separated by a space, where N is the number of regions and M is the number of roads.
• Each of the following M lines contains two integers representing a bidirectional road connecting two regions.

You can assume that the regions are numbered from 1 to N.

outputFormat

Output a single integer to stdout which denotes the minimum number of gifts required, according to the strategy discussed.

4 3
1 2
2 3
3 4

3