Minimum Connections to Add

You are given a network of computers with N nodes and M direct connections. Two computers are directly connected if there exists a direct link between them. The network is considered fully connected if there is a path between any two computers.

Your task is to determine the minimum number of additional direct connections required so that the entire network becomes fully connected.

The solution relies on discovering the number of connected components in the network. If there are \(c\) connected components, then you need to add at least \(\max(0, c - 1)\) connections to connect all components.

For example, if the network consists of 2 disconnected sub-networks (i.e. \(c = 2\)), then you need to add at least \(2 - 1 = 1\) connection.

inputFormat

The input is given via standard input (stdin). The first line contains two integers \(N\) and \(M\), representing the number of computers and the number of existing direct connections, respectively. Each of the next \(M\) lines contains two integers \(u\) and \(v\) indicating a direct connection between computer \(u\) and computer \(v\).

outputFormat

Output a single integer on standard output (stdout): the minimum number of additional connections required to make the network fully connected.

4 2
1 2
3 4

1