C1278 [JSOI2015]最小表示

内存限制:256 MB 时间限制:1000 ms

题目描述

【故事背景】

还记得去年 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$ 的有向边。

输入数据保证,任意两点间只会有至多一条边存在。

$N \le 30,000,M \le 100,000$

输出

输出一行包含一个整数,表示 JYY 最多可以删掉的边数。

样例

样例输入 1

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

样例输出 1

2

提示