题目描述

有 $n$ 个检测点，编号为 $1$ 到 $n$，以及 $m$ 条单向管道。每条管道都从编号较小的检测点通向编号较大的检测点，并且管道中的水最终都能到达检测点 $n$。两个检测点之间可能有多条方向相同的管道。

所有入度为 $0$ 的检测点都是排污起点，检测点 $n$ 是终点。一条排污路线是从任意排污起点出发，沿管道到达检测点 $n$ 的完整路线。

两条路线只要经过的检测点不同，或使用的管道不同，就视为不同路线。因此，连接同一对检测点的多条管道也需要分别计算。

一条管道的压力等于经过它的不同排污路线数量。请计算所有管道中的最大压力。

输入格式

第一行包含两个整数 $n,m$。

接下来 $m$ 行，每行包含两个整数 $x,y$，表示一条从检测点 $x$ 通向检测点 $y$ 的管道。

输出格式

输出一个整数，表示所有管道中的最大压力。

样例

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$
• 对于每条管道，$1 \le x<y \le n$
• 保证每条管道中的水最终都能到达检测点 $n$
• 保证答案不超过 $2^{31}-1$