Connect the Provinces

You are given a country with N provinces and a list of bidirectional roads connecting some pairs of provinces. Your task is to determine the minimum number of new roads that must be built in order to connect all the provinces so that there is a path between any two provinces.

Formally, if the given roads form k connected components, you need to output \( k-1 \) new roads so that the entire graph becomes connected. You may assume that building a road between any two provinces is allowed.

Hint: Use graph traversal algorithms such as DFS or BFS, or a Union-Find data structure to count the number of connected components.

The input may contain multiple test cases. The end of input is indicated by a test case where both N and M are 0.

inputFormat

The input consists of one or more test cases. Each test case starts with a line containing two integers N and M separated by a space, where \( N \) (1 ≤ N ≤ 10⁵) is the number of provinces and \( M \) (0 ≤ M ≤ 10⁵) is the number of roads. The following M lines each contain two integers A and B, representing a road connecting province A and province B.

The input terminates when a line with "0 0" is encountered, which should not be processed.

outputFormat

For each test case, output a single integer on a new line — the minimum number of new roads needed to connect all the provinces.

## sample

5 3
1 2
2 3
4 5
0 0

1

</p>