[JSOI2015] 最小表示
题目背景
还记得去年 JYY 所研究的强连通分量的问题吗?去年的题目里,JYY 研究了对于有向图的“加边”问题。对于图论有着强烈兴趣的 JYY,今年又琢磨起了“删边”的问题。
题目描述
对于一个 $N$ 个点(每个点从 $1$ 到 $N$ 编号),$M$ 条边的有向图,JYY 发现,如果从图中删去一些边,那么原图的连通性会发生改变;而也有一些边,删去之后图的连通性并不会发生改变。
JYY 想知道,如果想要使得原图任意两点的连通性保持不变,我们最多能删掉多少条边呢?
为了简化一下大家的工作量,这次 JYY 保证他给定的有向图一定是一个有向无环图(JYY:大家经过去年的问题,都知道对于给任意有向图的问题,最后都能转化为有向无环图上的问题,所以今年 JYY 就干脆简化一下大家的工作)。
输入输出格式
输入格式
第一行包含两个正整数 $N$ 和 $M$。
接下来 $M$ 行,每行包含两个 $1$ 到 $N$ 之间的正整数 $x_i$ 和 $y_i$,表示图中存在一条从 $x_i$ 到 $y_i$ 的有向边。
输入数据保证,任意两点间只会有至多一条边存在。
输出格式
输出一行包含一个整数,表示JYY最多可以删掉的边数。
输入输出样例
输入样例 #1
5 6
1 2
2 3
3 5
4 5
1 5
1 3
输出样例 #1
2
说明
### 样例解释
一种合法方案为删去 $1\rightarrow 5$ 和 $1\rightarrow 3$。容易证明没有比 $2$ 更优的答案。
### 数据范围
对于 $100\%$ 的数据,$1 \leq N\leq 3\times 10^4$,$0 \leq M\leq 10^5$。