小S是Q国交通部的部长，他最近在为一批物资的运输线路发愁。

Q国有 $N$ 个城市，由 $N-1$ 条双向道路连接，其中第 $i$ 条道路连接了城市 $i$ 和城市 $i+1$，这些道路通过所花费的时间均为 $1$。

现在有 $M$ 条运输物资的线路，第 $i$ 条线路是从 $u_i$ 号城市向 $v_i$ 号城市运输的。

现在因为Q国执行了圣光的教义，诸神可以在两个城市间建立一座传送阵。这座传送阵可以连接任意两座城市，而且从其中一座城市可以瞬间移动到另一座城市。

现在小S想要尽快将这些运输方案完成，他想知道最优情况下最后到达目的地的运输方案最早是多少。

输入格式

第一行为2个正整数 $N$、$M$。

接下来 $m$ 行，每行两个正整数 $u_i$、$v_i$。

输出格式

输出最优情况下最后到达目的地的运输方案的时间。

样例一

input

5 2
1 3
2 4

output

1

explanation

在 $2$ 号城市与 $3$ 号城市建立传送阵，这样运输方案时间最长的只需要 $1$ 点时间就可以了。

样例二

input

9 8
3 5
4 1
8 4
8 4
8 5
8 9
4 9
8 2

output

3

限制与约定

对于 $100\texttt{%}$ 的数据：$1 \leq N、M \leq 525010$，$1 \leq u_i、v_i \leq N$。

时间限制：$1\texttt{s}$

空间限制：$128\texttt{MB}$