UOJ Logo Zijian Online Judge

ZOJ

#6. 线路规划

统计

小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

限制与约定

测试数据编号$N、M$
1$=100$
2$=200$
3$=501$
4$=2501$
5$=5210$
6$=5210$
7$=52501$
8$=152501$
9$=252501$
10$=525010$

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

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

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