#3494. PA2010 Planning the Roadworks

题目描述

给定一张n个点m条边的有向图请找到一个极大的可行边集,使得这个边集中的边被去掉后,原图中任意两个点i,j的连通性不变.

请输出边集中的边的数目及可行方案.

1<=n<=5000,1<=m<=100000,保证没有重边和自环.

输入格式

输出格式

样例

样例输入

5 6  

1 2  

1 3  

2 3  

3 2  

2 4  

3 4  

样例输出

2  

数据范围与提示