题目描述

你被困在一个如下图所示的迷宫里，你所在的位置在房间 $\red 1$，迷宫的出口在房间 $\red N$ 编 号相邻的房间之间是没有墙阻隔的

这个迷宫由于地震影响，其中有 $\red M$ 座墙已经倒塌了

每一步你可以从你所在的房间走到旁边的没有墙阻隔的一个房间，求走出这个迷宫最少 需要多少步

输入格式

第一行为一个数字 $\red N$，表示出口在房间 $\red N$，满足 $\red {1≤N≤10^{15}}$

第二行为一个数字 $\red M$，表示有 $\red M$ 座墙已经倒塌了

接下来 $\red M$ 行，每行两个正整数 $\red A$ 和 $\red B$，表示房间 $\red A$ 和房间 $\red B$ 之间的墙已经倒塌了，保 证输入合法

输出格式

输出文件的第一行为最少需要的步数

样例

输入样例

31
9
4 15 
10 25
13 30 
1 6 
2 9
6 19 
9 24 
10 27 
1 4

输出样例

6

提示

样例说明

路线为 $\red {1-4-15-14-13-30-31}$