There is an undirected graph $G$ with $n$ vertices and $m$ edges. Every time, you can select several edges and delete them. The edges selected must meet the following condition: let $G^\prime$ be graph induced from these edges, then every connected component of $G^\prime$ has at most one cycle. What is the minimum number of deletion needed in order to delete all the edges.

There are multiple test cases. The first line of input contains an integer $T$ indicating the number of test cases. For each test case:

The first line contains two integers $n$ and $m$ $(1 \le n \le 2000, 0 \le m \le 2000)$ -- the number of vertices and the number of edges.

For the next $m$ lines, each line contains two integers $u_i$ and $v_i$, which means there is an undirected edge between $u_i$ and $v_i$ $(1 \le u_i, v_i \le n, u_i \ne v_i)$.

The sum of values of $n$ in all test cases doesn't exceed $2 \cdot 10^4$. The sum of values of $m$ in all test cases doesn't exceed $2 \cdot 10^4$.

For each test case, output the minimum number of deletion needed.

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

1
2
1

BestCoder Round #74 (div.1)