Deletion

给出一个$n$个点$m$条边的无向图$G$. 每次你可以选择一些边, 从图中删掉. 要求选出来的边构成的子图的每个连通块最多只有一个环. 问最少需要删几次才能把所有边都删掉.

输入包含多组数据. 第一行有一个整数$T$, 表示测试数据的组数. 对于每组数据:

第一行包含两个整数$n$和$m$ $(1 \le n \le 2000, 0 \le m \le 2000)$, 表示节点数目和边的数目.

接下来$m$行, 每行包含两个整数$u_i$和$v_i$, 表示$u_i$和$v_i$之间有一条无向边 $(1 \le u_i, v_i \le n, u_i \ne v_i)$.

输入数据中$n$的和不超过$2\cdot 10^4$. 输入数据中$m$的和不超过$2\cdot 10^4$.

对于每组数据, 输出最小删除次数.

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