Minimum Edge Addition for Graph Connectivity

You are given an undirected graph with n nodes and m edges. The nodes are numbered from 1 to n. Your task is to determine the minimum number of edges you need to add in order to make the graph connected.

A graph is connected if there is a path between any two nodes. It can be shown that the number of edges required is components - 1, where components is the number of connected components in the graph.

In mathematical terms, if the graph has k connected components, then the minimum number of extra edges needed is \[ E = k - 1 \] provided that k > 0.

The input begins with an integer T representing the number of test cases. For each test case, the first line contains two integers n and m, and then m subsequent lines follow with two integers u and v describing an edge between node u and node v.

Output one line for each test case with the minimum number of edges required.

inputFormat

The first line of the input contains a single integer T, the number of test cases. The description of each test case is as follows:

• The first line contains two space-separated integers n (the number of nodes) and m (the number of edges).
• The next m lines each contain two space-separated integers u and v indicating that there is an edge between node u and node v.

All input is read from standard input (stdin).

outputFormat

For each test case, output a single integer on a new line: the minimum number of edges required to make the graph connected. The output should be written to standard output (stdout).

## sample

2
4 2
1 2
2 3
5 1
1 2

1
3

</p>