Village-to-Village Connectivity

The city government has surveyed the urban road network and obtained a table listing pairs of towns that are directly connected by roads. The goal of the "Village-to-Village Connectivity Project" is to ensure full connectivity among all towns in the city, meaning that there exists a path between any two towns (directly or indirectly).

Given the current list of roads, your task is to compute the minimum number of additional roads required so that every pair of towns is connected. Note that the minimum additional roads needed is given by the formula:

\( \text{Minimum additional roads} = C - 1 \)

where \( C \) is the number of connected components in the graph.

inputFormat

The first line contains two integers \( n \) and \( m \), where \( n \) is the number of towns and \( m \) is the number of existing roads.

The following \( m \) lines each contain two integers \( u \) and \( v \) indicating that there is a road directly connecting town \( u \) and town \( v \). The towns are numbered from 1 to \( n \).

outputFormat

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

sample

4 2
1 2
3 4

1