Minimum New Connections

You are given an undirected graph representing a network of servers. Each server is represented by a node and each existing connection is represented by an edge. Your task is to determine the minimum number of new connections (edges) required to connect all the servers such that there is a path between any two servers.

This problem can be solved by identifying the number of connected components \(C\) in the graph. Since connecting \(C\) components into a single connected network requires at least \(C-1\) additional connections, the answer is \(C-1\).

Input Format: The input begins with an integer \(T\) (the number of test cases). Each test case starts with two integers \(n\) and \(m\), representing the number of servers and the number of existing connections, respectively. The following \(m\) lines each contain two integers \(u\) and \(v\), indicating a connection between server \(u\) and server \(v\>.

Output Format: For each test case, output a single integer representing the minimum number of new connections needed to create a fully connected network.

inputFormat

The input is given via standard input (stdin). It begins with an integer (T) indicating 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 servers and (m) is the number of existing connections.
• The next (m) lines each contain two space-separated integers (u) and (v) representing a direct connection between servers (u) and (v).

outputFormat

For each test case, output one integer on a new line — the minimum number of new connections required to make the network fully connected.## sample

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

1
1
4