J14 实践-5 最小表示

题目描述

还记得去年 $\text{JYY}$ 所研究的强连通分量的问题吗？去年的题目里，$\text{JYY}$ 研究了对于有向图的“加边”问题。对于图论有着强烈兴趣的 $\text{JYY}$，今年又琢磨起了“删边”的问题。

对于一个 $N$ 个点（每个点从 $1$ 到 $N$ 编号），$M$ 条边的有向图，$\text{JYY}$ 发现，如果从图中删去一些边，那么原图的连通性会发生改变；而也有一些边，删去之后图的连通性并不会发生改变。

$\text{JYY}$ 想知道，如果想要使得原图任意两点的连通性保持不变，我们最多能删掉多少条边呢？

为了简化一下大家的工作量，这次 $\text{JYY}$ 保证他给定的有向图一定是一个有向无环图（ $\text{JYY}$：大家经过去年的问题，都知道对于给任意有向图的问题，最后都能转化为有向无环图上的问题，所以今年 $\text{JYY}$ 就干脆简化一下大家的工作）。

输入格式

输入一行包含两个正整数 $N$ 和 $M$ 。

接下来M行，每行包含两个 $1$ 到 $N$ 之间的正整数 $x_i$ 和 $y_i$，表示图中存在一条从 $x_i$ 到 $y_i$ 的有向边。

输出格式

输出一行包含一个整数，表示 $\text{JYY}$ 最多可以删掉的边数。

样例输入

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

样例输出

2

样例分析

一种合法方案为删去 $1\rightarrow 5$ 和 $1\rightarrow 3$。容易证明没有比 $2$ 更优的答案。

数据范围

对于 $100\%$ 的数据：输入数据保证，任意两点间只会有至多一条边存在，$N \leq 30000$，$M \leq 100000$。