Problem #3738 - ECNU Online Judge

单点时限: 1.0 sec

内存限制: 256 MB

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

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

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

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

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

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

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

接下来的 $m$ 行，每行两个整数 $x_{i}, y_{i} (1 \leq x_{i}, y_{i} \leq n, x_{i} \neq y_{i})$ 表示有一条从 $x_{i}$ 到 $y_{i}$ 的有向边。

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

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

Input

Output

0
1

27 人解决，66 人已尝试。

35 份提交通过，共有 325 份提交。

6.4 EMB 奖励。

创建: 5 年，3 月前.

修改: 5 年，3 月前.

最后提交: 4 年，5 月前.

3738. 最简边集