题目描述

孙悟空每天都要准时到达王宫上朝，否则会被玉帝降罪。然而，孙悟空有一个问题，他总是喜欢赖床。为了保住自己的职位和避免惩罚，他决定利用他的神通之一————筋斗云。
王宫和孙悟空的住处可以看作是一座巨大的迷宫，每个房间之间的距离都是固定的。孙悟空可以利用筋斗云每秒钟飞行2^k千米的速度（其中k是任意自然数），但是筋斗云飞行的总距离不能超过筋斗云的极限距离。
现在，孙悟空想知道，他至少需要多少时间才能从自己的住处飞到王宫，以便准时上朝。你能帮助他解决这个问题吗？保证从孙悟空的住处（1）到王宫（n）之间至少存在一条路径。

输入格式：

第一行两个整数n，m，表示迷宫内的房间数和房间之间路的条数。
接下来m行每行两个数字u，v，表示一条连接房间u到v的有向路。

输出格式：

一行一个数字，表示孙悟空到王宫的最少秒数。

输入样例#1：

4 4
1 1
1 2
2 3
3 4

输出样例#1：

1

说明/提示

【样例解释】
1→1→2→3→4，总路径长度为 4 千米，直接使用一次筋斗云即可。
【数据范围】
50% 的数据满足最优解路径长度 ⩽1000；
100% 的数据满足 n⩽50，m⩽10000，最优解路径长度 ⩽ maxlongint。