题目描述

某校要求学生每天早上 $7:00$ 之前到校，令学生十分无语却又无可奈何。

小懒同学对此更是深恶痛绝。为了不受处分，小懒买了一辆自行车。这可不是普通的自行车，它是一款神奇的“快速米”变速自行车，骑上它，每分钟可以行驶 $2^k$ 千米（$k$ 是一个非负整数，每分钟开始前可以通过变速器任意设置 $k$ 的值）。

为了能够多睡会懒觉，小懒绘制了包含家和学校的地图，想要找到一条合适的路线，可以用最短的时间到达学校。

图中一共有 $n$ 个点，编号为 $1$ ~ $n$。小懒的家在 $1$ 号点，学校在 $n$ 号点。一共有 $m$ 条路，每条路都是单行道，长度均为 $1$ 千米。可能有自环。

从家到学校，小懒最少需要多少分钟呢？

注：除了路上行驶花费时间，其他如设置 $k$ 值等任何行为均不花费时间。每分钟行驶恰好 $2^k$ 千米，中途可能经过学校。行驶结束恰好到学校，才视为到达学校。

输入格式

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

接下来 $m$ 行：每行两个整数 $u,v$，表示从点 $u$ 到点 $v$ 有一条单向道路。

输出格式

一个整数，表示答案。

样例1输入

4 4
1 1
1 2
2 3
3 4

样例1输出

1

样例1解释

设置 k = 2 ，按以下路线行驶，1 分钟即可到达：

1 ---> 1 ---> 2 ---> 3 ---> 4

样例2输入

4 3
1 2
2 3
3 4

样例2输出

2

样例2解释

初始设置 k = 0，花费 1 分钟：1 ---> 2

此时设置 k = 1，再花费 1 分钟：2 ---> 3 ---> 4

数据范围

$20\%$ 的数据：n 个点构成一条单向链，没有自环；

$50\%$ 的数据：满足条件的路径长度 $≤ 1024$；

$100\%$ 的数据：$2 ≤ n ≤ 50$，$m ≤ 10,000$，数据保证家到学校至少有一条路线，且满足条件的路径长度 $< 2^{63}$。