#P3494. PA2010 Planning the Roadworks

PA2010 Planning the Roadworks

Planning the Roadworks

题目描述

Bajtowa Góra 有 nn 个路口,由 mm 条单向道路连接。市政府准备同时封闭一些道路进行维修。对于任意两个路口 u,vu,v,如果封路前可以沿单向道路从 uu 到达 vv,封路后也必须可以从 uu 到达 vv。

求最多可以同时封闭多少条道路。

输入格式

第一行有两个整数 n,mn,m,分别表示路口数和道路数。路口编号为 11 至 nn。

接下来 mm 行,每行有两个整数 ai,bia_i,b_i,表示一条从 aia_i 到 bib_i 的单向道路。

输出格式

输出一行一个整数,表示最多可以同时封闭的道路条数。

样例

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

样例 1 可以封闭第 22 条和第 66 条道路。第 33、44 条道路均须保留,另外至少要保留一条从路口 11 出发的道路和一条通往路口 44 的道路,因此最多可以封闭两条。

3 2
1 2
2 3
0

数据范围

1≤n≤50001\le n\le 5000,1≤m≤1051\le m\le 10^5,1≤ai,bi≤n1\le a_i,b_i\le n,ai≠bia_i\ne b_i。同一有序路口对最多出现一次。