问题 25632 --奶牛交通

25632: 奶牛交通

时间限制: 1 Sec  内存限制: 128 MB
提交: 26  解决: 17
[提交][状态][讨论版][数据上传:][下载FPS1元][下载测试数据1元][172kb]

题目描述

由于奶牛数量的大膨胀,牧场里通往牛棚的道路不堪重负,为了缓解在挤奶高峰时间的交通堵塞,农夫约翰决定找出最拥挤的道路来整治。

    牧场里有M (1 ≤ M ≤ 50000)条单行的道路,N (1 ≤ N ≤ 5000)个路口(从1N标号),每条道路连接了两个不同的路口。牛棚就在N号路口上。.每一条道路都由编号较小的路口通向编号较大的路口,所以在道路网络里将不会出现环,而且犹如老话所讲的那样:条条道路通牛棚。注意同一对路口上可能出现一条以上的道路。

    在挤奶的高峰期,一些奶牛会从放牧点走向牛棚。那些只出不进的路口都是放牧点。一个放牧点连向牛棚的道路序列构成一条路径,每条路径上都会有一头不同的奶牛通过。

    帮助约翰找到最拥挤的那条道路上通过的奶牛数量。我们保证结果不会超过一个有符号的 32 位整数。

输入

第一行:两个用空格分开的整数:NM

第二行到第M + 1行:两个用空格分开的整数表示一条道路连接的两个路口的编号

输出

第一行:最拥挤的道路上通过的路径数量

样例输入

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

样例输出

4

提示


(最拥挤的道路是(6,7),一共有四条路径:



13467



13567



23467


   23567

来源

[提交][状态]