Minimum Roads to Connect

You are given a graph with N vertices and M edges, representing cities and bidirectional roads respectively. Your task is to determine the minimum number of additional roads needed to connect all the cities so that there is a path between any two cities.

The input graph may be disconnected. If the graph has k connected components, then you need to add exactly \(k-1\) roads to connect all components.

Note: Use efficient union-find (disjoint set union) algorithms to solve the problem for large inputs.

inputFormat

The input is read from stdin and has the following format:

N M
u1 v1
u2 v2
... 
 uM vM

Where:

• N is the number of vertices (cities), with vertices numbered from 1 to N.
• M is the number of roads (edges).
• Each of the next M lines contains two integers \(u_i\) and \(v_i\) representing a road connecting vertices \(u_i\) and \(v_i\).

outputFormat

Output a single integer to stdout representing the minimum number of additional roads required to make the entire graph connected.

6 4
1 2
2 3
4 5
5 6

1