题目描述

随着牛的数量增加，农场的道路的拥挤现象十分严重，特别是在每天晚上的挤奶时间。为了解决这个问题，FJ 决定研究这个问题，以能找到导致拥堵现象的瓶颈所在。

牧场共有 $M$ 条单向道路，每条道路连接着两个不同的交叉路口，为了方便研究，FJ 将这些交叉路口编号为 $1\sim N$，而牛圈位于交叉路口 $N$。任意一条单向道路的方向一定是是从编号低的路口到编号高的路口，因此农场中不会有环型路径。同时，可能存在某两个交叉路口不止一条单向道路径连接的情况。

在挤奶时间到来的时候，奶牛们开始从各自的放牧地点回到牛圈。放牧地点是指那些没有道路连接进来的路口（入度为 $0$ 的顶点）。

现在请你帮助 FJ 通过计算从放牧点到达牛圈的路径数目来找到最繁忙的道路，即求出所有可行路径中通过某条道路的最大值。

输入格式

第一行两个正整数 $N,M$。

下面 $M$ 行，每行两个正整数 $U_i,V_i$，表示一条有向道路 $U_i \to V_i$。

输出格式

一行一个整数表示答案。

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

4

提示

样例解释：

四条最优路径如下。

1 -> 3 -> 4 -> 6 -> 7
1 -> 3 -> 5 -> 6 -> 7
2 -> 3 -> 4 -> 6 -> 7
2 -> 3 -> 5 -> 6 -> 7

对于 $100\%$ 的数据，$1 \le N \le 5 \times 10^3$，$1 \le M \le 5 \times 10^4$，$1 \le U_i,V_i \le N$。