#P3494. PA2010 Planning the Roadworks
PA2010 Planning the Roadworks
Planning the Roadworks
题目描述
Bajtowa Góra 有 个路口,由 条单向道路连接。市政府准备同时封闭一些道路进行维修。对于任意两个路口 ,如果封路前可以沿单向道路从 到达 ,封路后也必须可以从 到达 。
求最多可以同时封闭多少条道路。
输入格式
第一行有两个整数 ,分别表示路口数和道路数。路口编号为 至 。
接下来 行,每行有两个整数 ,表示一条从 到 的单向道路。
输出格式
输出一行一个整数,表示最多可以同时封闭的道路条数。
样例
5 6
1 2
1 3
2 3
3 2
2 4
3 4
2
样例 1 可以封闭第 条和第 条道路。第 、 条道路均须保留,另外至少要保留一条从路口 出发的道路和一条通往路口 的道路,因此最多可以封闭两条。
3 2
1 2
2 3
0
数据范围
,,,。同一有序路口对最多出现一次。