给定一个包含 $n$ 个顶点和 $m$ 条边的有向图。图的顶点编号从 $1$ 到 $n$，且每条边都从编号较小的顶点指向编号较大的顶点。

如果一个路径序列满足以下条件，我们称其为有趣的：

• 每条路径都从顶点 $1$ 开始，到顶点 $n$ 结束；
• 每条路径都包含至少一条在之前所有路径中未出现过的边。

求最长的有趣路径序列的长度。

输入格式

输入的第一行包含两个整数 $n$ 和 $m$ ($2 \le n \le 10^6$, $0 \le m \le 10^6$)，分别表示图中顶点的数量和边的数量。

接下来的 $m$ 行，每行包含两个整数 $a$ 和 $b$ ($1 \le a < b \le n$)，描述一条从顶点 $a$ 指向顶点 $b$ 的有向边。每对 $(a, b)$ 在输入中最多出现一次。

输出格式

输出一个整数，表示最长的有趣路径序列的长度。

样例

样例输入 1

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

样例输出 1

4

样例输入 2

5 3
1 3
2 3
2 5

样例输出 2

0

说明

对于第一个样例，一个长度为 $4$ 的有趣路径序列可以是：

• $1 \to 3 \to 5$（边 $1 \to 3$ 第一次被使用），
• $1 \to 2 \to 3 \to 5$（边 $1 \to 2$ 第一次被使用），
• $1 \to 3 \to 4 \to 5$（边 $3 \to 4$ 第一次被使用），
• $1 \to 2 \to 4 \to 5$（边 $2 \to 4$ 第一次被使用）。

在第二个样例中，不存在从顶点 $1$ 到顶点 $5$ 的路径。