由于奶牛数量的大膨胀,牧场里通往牛棚的道路不堪重负,为了缓解在挤奶高峰时间的交通堵塞,农夫约翰决定找出最拥挤的道路来整治。
牧场里有M (1 ≤ M ≤ 50000)条单行的道路,N (1 ≤ N ≤ 5000)个路口(从1到N标号),每条道路连接了两个不同的路口。牛棚就在N号路口上。.每一条道路都由编号较小的路口通向编号较大的路口,所以在道路网络里将不会出现环,而且犹如老话所讲的那样:“条条道路通牛棚”。注意同一对路口上可能出现一条以上的道路。
在挤奶的高峰期,一些奶牛会从放牧点走向牛棚。那些只出不进的路口都是放牧点。一个放牧点连向牛棚的道路序列构成一条路径,每条路径上都会有一头不同的奶牛通过。
帮助约翰找到最拥挤的那条道路上通过的奶牛数量。我们保证结果不会超过一个有符号的 32 位整数。
第一行:两个用空格分开的整数:N和M
第二行到第M + 1行:两个用空格分开的整数表示一条道路连接的两个路口的编号7 7
1 3
3 4
3 5
4 6
2 3
5 6
6 7
4
(最拥挤的道路是(6,7),一共有四条路径:
1→3→4→6→7
1→3→5→6→7
2→3→4→6→7
2→3→5→6→7)