农场奶牛数量激增，使通往牛棚的小路严重拥堵。Farmer John 要研究瓶颈，缓解挤奶时的“堵车”。

牧场有 $M$（$1 \le M \le 50,000$）条单向路，每条连接 $N$（$1 \le N \le 5,000$）个编号 $1..N$ 交点中的两个不同点，牛棚在 $N$。各路通向更大编号，故无环，所谓条条路通牛棚。一对点可能多路相连。

挤奶高峰，牛从各自放牧点去牛棚。放牧点恰为没有入路的交点。“路径”定义为放牧点到牛棚的路序列。

求包含某一条路的可能路径数的最大值，以找最繁忙路。保证答案能装入有符号 32 位整数。

输入格式

第 1 行：空格分隔整数 $N$、$M$。

第 $2..M+1$ 行：空格分隔两个交点。

输出格式

第 1 行：通过任一条路的路径数最大值。

样例

输入格式 1

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

输出格式 1

4

说明

通往牛棚的四条可能路径如下：

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

题目来源：USACO 2007 年 3 月。