Minimum Tracks to Connect Stations

You are given T test cases. In each test case, there are N stations numbered from 1 to N and M existing undirected tracks connecting pairs of stations. Your task is to determine the minimum number of additional tracks required so that there is a path between every pair of stations.

Formally, let the number of connected components in the graph be \(C\). To connect all components, you need at least \(C - 1\) tracks. Use union-find (disjoint set union) or any other method to compute the number of connected components and then output \(C - 1\).

Input and Output Format: The input is read from standard input and the output should be written to standard output.

inputFormat

The first line contains an integer T, the number of test cases. For each test case:

• The first line contains two space-separated integers N and M, where N is the number of stations and M is the number of existing tracks.
• The next M lines each contain two space-separated integers u and v indicating that there is a track connecting station u and station v.

You can assume that 1 ≤ u, v ≤ N and the graph may be initially disconnected.

outputFormat

For each test case, output a single integer on a new line denoting the minimum number of tracks that must be added so that all stations are connected.

Note: The answer for each test case is \(C - 1\), where \(C\) is the number of connected components in the graph.

## sample

2
4 2
1 2
3 4
5 3
1 2
2 3
4 5

1
1

</p>