Taco: Connecting Towns

You are given n towns and m existing roads. Each road connects two distinct towns. The goal is to determine the minimum number of new roads required so that every town is connected to every other town directly or indirectly. In graph theory terms, you need to calculate the number of connected components in an undirected graph; the answer is given by \(\text{number of components} - 1\).

This problem is essential for planning and optimization, ensuring that isolated networks are connected efficiently.

inputFormat

The input is given from standard input. The first line contains two integers \(n\) and \(m\) where \(n\) is the number of towns and \(m\) is the number of existing roads. Each of the next \(m\) lines contains two integers \(u\) and \(v\) indicating there is a road connecting town \(u\) and town \(v\).

outputFormat

Output a single integer representing the minimum number of new roads required to connect all the towns.

4 2
1 2
3 4

1