Minimum Edges to Remove

You are given a graph with n nodes and m edges. The graph may contain cycles. Your task is to determine the minimum number of edges that must be removed so that the resulting graph becomes a forest (i.e. a collection of trees with no cycles). In other words, you need to remove extra edges that introduce cycles.

A tree with n nodes has exactly n-1 edges. Given a connected component of the graph, if it has k nodes and e edges, then it must have exactly e - (k - 1) extra edges, which are to be removed. The overall answer is the sum of extra edges over all connected components.

The problem can be solved using Union-Find (Disjoint Set Union) data structure. For every edge, if the two vertices are already connected, then that edge creates a cycle and should be counted as an extra edge. Otherwise, the sets are merged.

Formally, for each test case, you are given:

• An integer n (number of nodes) and an integer m (number of edges).
• m pairs of integers u v which denote an edge between node u and node v.

Your task is to output one integer for each test case, representing the minimum number of edges to remove.

The formula for a connected component is given as:

[ \text{extra_edges} = e - (k - 1) ]

where e is the original number of edges in the component and k is the number of nodes in that component.

inputFormat

The first line contains a single integer T representing 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.

Each of the next m lines contains two integers u and v representing an edge between nodes u and v (1-indexed).

outputFormat

For each test case, output a single integer on a new line representing the minimum number of edges that must be removed so that the graph becomes a forest.

## sample

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

0
2

</p>