题目描述

随着人们对产品需求的日益增长，市里建造了很多工厂，生产各类产品。

对于工厂的污水排放，环保部门有严格的要求，污水必须从专门建造的排污管道中排放，并且只有在规定的时间才能排污。纵横交错的管道形成了管道网络。在管道网络的交叉点上，环保部门设有检测点，用于检测管道中的污水是否达标。

网络中共有 $N$ 个检测点（编号为 $1 \sim N$）和 $M$ 条单向污水流通管道，每条管道连接两个不同的检测点，某些检测点之间可能存在多条直接连接的管道。

所有的单向管道都保证从编号较小的检测点指向编号较大的检测点，且所有的管道中的污水最终都可以流到编号为 $N$ 的检测点，该检测点统一处理所有的污水。

所有只有管道流出，没有管道流入的检测点上，都设有一座工厂，每天凌晨，各个工厂将一起向排污管道中排放污水。

从污水排放的起点，到污水排放的终点，形成了多条排放路线。被最多的排放路线经过的污水管道，将承受最大的压力。

请你编程计算出，这些压力最大的管道，被多少条污水排放路线经过了。

不同路线的定义是： 如果两条从排污起点到排污终点的路线上，有至少 $1$ 个点是不同的，或者有至少 $1$ 条管道是不同的，就认为是不同的排污路线。

输入格式

第 $1$ 行读入 $2$ 个整数 $N, M$。

接下来 $M$ 行，每行读入两个整数 $x, y$，表示两点之间有一条单向的管道。

输出格式

输出 $1$ 个整数，表示压力最大的管道，被不同排污路线经过的数量。

题目保证测试数据的输出结果不超过 $2^{31} - 1$。

样例

输入

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

输出

4

输入

5 5
1 3
2 3
3 4
4 5
4 5

输出

4

数据范围

对于 $20\%$ 的数据，满足 $1 \le N \le 10$，$1 \le M \le 20$。

对于 $100\%$ 的测试数据，满足 $1 \le N \le 1000$，$1 \le M \le 15000$。