Minimum Additional Connections

You are given a network with n nodes (servers) and m undirected connections between them. Two nodes are in the same connected component if there is a path between them. The task is to determine the minimum number of additional connections required to make the entire network connected, i.e. to connect all nodes.

In graph theory terms, if the graph has c connected components, you need to add at least \(c - 1\) new edges in order to connect all the components into one. Your goal is to compute \(c - 1\) given the input graph.

inputFormat

The first line of input contains two integers \(n\) and \(m\) — the number of nodes and the number of connections, respectively. The following \(m\) lines each contain two integers \(a\) and \(b\) representing an undirected connection between nodes \(a\) and \(b\). Nodes are numbered from 1 to \(n\).

outputFormat

Output a single integer: the minimum number of additional connections required to make the network connected.

1 0

0