题目描述

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

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

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

现在请你帮助FJ计算哪条道路是最繁忙的（途径这条道路的路径总数最多）。

输入格式

第一行，两个整数 N 和 M。

接下来 M 行，每行两个整数，表示每条道路的两端编号。

输出格式

一行输出一个数，表示最繁忙的道路的途径路径总数。

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

4

提示

样例总共有以下4条可能的路径：

1−3−4−6−7，1−3−5−6−7，2−3−4−6−7，2−3−5−6−7

其中最繁忙的道路是6−7，途径这条道路共有4条路径。

2 1
1 2

1

10 9
1 10
2 10
3 10
4 10
5 10
6 10
7 10
8 10
9 10

1

数据范围

$1\le N\le 1,000$，$1\le M\le 50,000$。

保证答案不超过 $2^{31}-1$