牛数急増で納屋への道が大渋滞です。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 月。