跑路

• 时间限制：1 秒
• 内存限制：128 MiB

题目描述

小 A 的家到公司之间的道路构成一个有向图。小 A 的家是顶点 $1$，公司是顶点 $n$，每条边的长度均为一千米。

小 A 有一台空间跑路器。每使用一秒，跑路器可以沿图中的一条有向路径前进恰好 $2^k$ 千米，其中 $k$ 可以是任意自然数。跑路器使用 32 位整数记录一次连续路线的信息，因此所采用路径的总长度不能超过 $2^{31}-1$ 千米。

求小 A 从家到公司最少需要多少秒。数据保证从顶点 $1$ 到顶点 $n$ 至少存在一条路径。

输入格式

第一行包含两个整数 $n,m$，分别表示顶点数和边数。

接下来 $m$ 行，每行包含两个整数 $u,v$，表示一条从 $u$ 指向 $v$ 的边。

输出格式

输出一个整数，表示从家到公司所需的最少秒数。

样例输入 1

4 4
1 1
1 2
2 3
3 4

样例输出 1

1

样例解释

可以沿 $1\to1\to2\to3\to4$ 前进，总长度为 $4$ 千米，因此只需使用一次跑路器。

数据范围

• $2\le n\le50$；
• $1\le m\le10^4$；
• $1\le u,v\le n$；
• 从顶点 $1$ 到顶点 $n$ 至少存在一条路径；
• 最优路线的总长度不超过 $2^{31}-1$。