Minimum Edge Removal to Preserve Connectivity

You are given a connected undirected graph. For each test case, you are given the number of nodes \(N\), the number of edges \(M\), and a list of \(M\) edges. Your task is to determine the minimum number of edges that can be removed from the graph such that the remaining graph stays connected.

Note that for a connected graph:

• If the graph is a tree (i.e. if \(M = N - 1\)), then removing any edge will disconnect the graph, so the answer is 0.
• If there is at least one cycle (i.e. if \(M > N - 1\)), then at least one edge in the cycle can be removed without breaking connectivity, so the answer is 1.

Mathematically, you can decide using the condition \(M > N - 1\). If it holds, then the answer is \(1\); otherwise, it is \(0\).

inputFormat

The first line contains an integer \(T\) denoting the number of test cases. The description of each test case is as follows:

1. The first line of each test case contains two integers \(N\) and \(M\), representing the number of nodes and edges respectively.
2. This is followed by \(M\) lines, each line containing two integers \(U\) and \(V\) which indicates that there is an undirected edge connecting node \(U\) and node \(V\).

It is guaranteed that the given graph is initially connected.

outputFormat

For each test case, output a single line containing one integer: the minimum number of edges that can be removed without disconnecting the graph.

## sample

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

1
0

</p>