3738. 最简边集

单点时限: 1.0 sec

内存限制: 256 MB

Cuber QQ 最近沉迷图论的研究。

他最近在研究有向无环图。他认为有向无环图中有很多边也是没有任何作用的。

Cuber QQ 定义一个有向无环图的最简边集是指保留最少的边,但需要保证原图中任意两点的联通性不会发生任何改变。

联通性不会发生任何改变具体来说,就是如果在原图中本来可以从结点 $A$ 到结点 $B$ ,那么在简化以后的图中也应该能从结点 $A$ 到结点 $B$ ;如果在原图中本来就不能可以从结点 $A$ 到结点 $B$ ,那么在简化以后的图中也无法从结点 $A$ 到结点 $B$ 。

现在 Cuber QQ 想知道,要将原图的边集变成原图的最简边集,需要删除多少条边。

输入格式

输入数据第一行包含一个整数 $T(1\le T\le 1000)$ ,表示数据组数。

对于每一组数据,第一行输入两个整数 $n,m(1\le n\le 2000,1\le m\le 50000)$ ,分别表示有向无环图的点数和边数。

接下来的 $m$ 行,每行两个整数 $x_i,y_i(1\le x_i,y_i\le n,x_i\neq y_i)$ 表示有一条从 $x_i$ 到 $y_i$ 的有向边。

保证给出的图不存在重边和自环,且 $\sum n\le 2000,\sum m\le 50000$ 。

输出格式

对于每一组数据输出一行一个整数,表示答案。

样例

Input
2
4 3
1 4
2 4
3 4
4 4
1 4
2 3
3 1
2 4
Output
0
1

27 人解决,64 人已尝试。

35 份提交通过,共有 273 份提交。

6.3 EMB 奖励。

创建: 6 月,3 周前.

修改: 6 月,3 周前.

最后提交: 2 月,2 周前.

来源: EOJ Monthly 2020.1

题目标签