Minimum Number of Edges to Connect Graphs

You are given multiple undirected graphs. For each graph, your task is to determine the minimum number of edges that must be added so that the graph becomes connected. In other words, if a graph has (k) connected components, you need to add (k-1) edges to connect them all.

For example, consider a graph with (n = 4) nodes and (m = 2) edges: ((1,2)) and ((3,4)). This graph has two connected components, so you will need to add (2 - 1 = 1) edge to connect the graph.

This problem can be effectively solved using the Disjoint Set Union (DSU) data structure.

inputFormat

The first line of input contains an integer (T), the number of test cases.

For each test case, the first line contains two integers (n) and (m) where (n) is the number of nodes and (m) is the number of edges in the graph. The next (m) lines each contain two integers (u) and (v) representing an undirected edge between node (u) and node (v). It is guaranteed that the nodes are numbered from 1 to (n).

outputFormat

For each test case, output a single integer on its own line—the minimum number of edges that need to be added to make the graph connected.## sample

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

1
1
2