Connecting Islands

You are given a set of islands numbered from 1 to N and a list of existing bridges connecting some pairs of islands. Your task is to determine the minimum number of new bridges required so that every island becomes reachable from any other island.

Recall that if there are k connected components, then the minimum number of new bridges needed is given by $$k - 1$$. Two islands belong to the same connected component if there exists a sequence of bridges connecting them.

inputFormat

The first line contains two integers N and M separated by a space, where N is the number of islands and M is the number of existing bridges.

The next M lines each contain two integers u and v separated by a space, indicating that there is a bridge between island u and island v.

Note: Islands are numbered from 1 to N.

outputFormat

Output a single integer on a line representing the minimum number of new bridges required to connect all the islands.

5 2
1 2
3 4

2