Connecting Intersections

You are given a city with n intersections and m existing bidirectional roads. Each road connects two intersections. Your task is to determine the minimum number of new roads required to ensure that all intersections are connected, i.e. there is a path between any two intersections.

Mathematically, if the graph has c connected components, then the answer is given by:

$$\text{New Roads Needed} = c - 1$$

You are to read the input from stdin and output the answer to stdout.

inputFormat

The input is provided via stdin as follows:

• The first line contains two integers n and m representing the number of intersections and the number of existing roads respectively.
• The next m lines each contain two integers u and v, indicating that there is a road connecting intersection u and intersection v.

Note: Intersections are numbered from 1 to n.

outputFormat

Output a single integer to stdout indicating the minimum number of new roads required to connect all intersections.

1 0

0