题目内容

在2077年小塔所在的世界可以简化成一条数轴，小塔在位置$1$上，而小塔的目的地在$n$。

小塔的每分钟可以走一米，他每次可以选择往左走或往右走，在这条数轴上，还存在$m$个传送装置，每个装置连接着数轴上的两个点$(u,v)$，当小塔走到具有装置的点$u$时，其可以选择传送到点$v$，$v$点同理且每次传送耗时为$0$。

小塔现在希望你能帮他规划一下路线使得其到达目的地的时间是最少的。

输入描述

第一行为$n,m$，表示目的地坐标和装置个数。

接下来有$m$行，每行为两个整数表示装置连接的两个点$u,v$。

$1≤ n ≤ 10^9 ,1≤ m ≤10^4 ,1≤u,v≤n$。

输出描述

输出为一行，表示小塔最少需要的时间。

样例1

输入

10 2
1 5
4 10

输出

1

说明

小塔首先在$1$依靠装置传送到位置$5$，然后小塔再向左走一米花费一分钟，达到$4$，再利用传送装置到达$10$，所以小塔所需的时间为$1$分钟。

样例2

输入

10 3
2 3
3 4
4 5

输出

6

说明

小塔先走到$2$，花费一分钟，然后连续传送到$5$。

小塔从$5$走到$10$需要五分钟。

所有小塔一共需要六分钟。