“有向汉诺塔”的游戏棋盘由编号为 $1$ 到 $N$ 的 $N$ 根柱子组成。在某些柱子对之间存在有向边，且总是从编号较小的柱子指向编号较大的柱子。初始时，在柱子 $1$ 上有 $K$ 个大小从 $1$ 到 $K$ 的圆盘，按从大到小的顺序（从底向上）排列。游戏的目标是将所有圆盘移动到柱子 $N$ 上。

在单次移动中，你可以将位于某根柱子 $A$ 顶部的圆盘移动到另一根柱子 $B$ 的顶部，前提是存在一条从柱子 $A$ 到柱子 $B$ 的路径（不一定是单条边），并且柱子 $B$ 为空，或者柱子 $B$ 当前顶部的圆盘比正在移动的圆盘大。路径上经过的柱子中已有的圆盘大小不影响移动。

你的任务是，给定一个有向汉诺塔棋盘，确定能实现游戏目标（即将所有 $K$ 个圆盘移动到柱子 $N$ 上）的最大 $K$ 值。可以证明，圆盘的最大数量总是有限的。

输入格式

输入的第一行包含两个整数：$N$ ($2 \le N \le 500$) 和 $M$ ($0 \le M \le N(N - 1)/2$)，分别表示柱子的数量和边的数量。

接下来的 $M$ 行，每行描述一条边，包含两个整数 $a_i$ 和 $b_i$ ($1 \le a_i < b_i \le N$)，表示柱子 $a_i$ 和 $b_i$ 之间有一条有向边。每对柱子在输入中最多出现一次。

输出格式

输出一个整数，表示在给定的有向汉诺塔棋盘上，能够将 $K$ 个圆盘从柱子 $1$ 移动到柱子 $N$ 的最大可能 $K$ 值。

样例

输入格式 1

5 4
1 2
2 3
3 4
4 5

输出格式 1

5

输入格式 2

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

输出格式 2

5

输入格式 3

2 0

输出格式 3

0

说明

在第一个样例中，将 $5$ 个圆盘从柱子 $1$ 移动到柱子 $5$ 的移动序列示例如下：

柱子 1: 54321, 5432, 543, 543, 54, 5 柱子 2: 1, 1, 3, 3, 3, 3, 3 柱子 3: 2, 21, 21, 21, 21, 21, 2, 2 柱子 4: 4, 4, 1, 1, 1 柱子 5: 5, 54, 54, 543, 5432, 54321

在第三个样例中，由于没有边，因此无法移动任何圆盘。