Minimum New Roads to Connect Kingdom

You are given a kingdom with n cities and m bidirectional roads connecting some pairs of cities. The cities are numbered from 1 to n. The existing road network might be disconnected, meaning that some cities cannot reach others. Your task is to determine the minimum number of new roads required to make the kingdom fully connected so that there is a path between every pair of cities.

Mathematical Formulation: Let \(C\) be the number of connected components in the graph representing the cities. The answer for each test case is \(C-1\), as connecting \(C\) components requires at least \(C-1\) new roads.

Input/Output: The input starts with an integer t representing the number of test cases. For each test case, the first line contains two integers n and m. Then follow m lines, each with two integers \(u\) and \(v\) that denote an existing road between cities \(u\) and \(v\). The output for each test case is a single integer representing the minimum new roads needed.

inputFormat

The first line of input contains a single integer t (1 \leq t \leq 10), which is the number of test cases.

For each test case, the first line contains two space-separated integers n and m (1 \leq n \leq 10^5, 0 \leq m \leq 10^5) where n is the number of cities and m is the number of existing roads. The following m lines each contain two space-separated integers u and v (1 \leq u,v \leq n, u \neq v) indicating there is a road connecting city u and city v.

outputFormat

For each test case, output a single line containing one integer—the minimum number of new roads required to connect all the cities in the kingdom.

2
6 3
1 2
2 3
4 5
4 0

2
3