题目描述

给定一张含 n 个顶点、m 条边的简单无向图，顶点编号为 1..n。

如果对任意 l < x < r，只要 l 和 r 连通，l 和 x 也一定连通，就称这张图是“和谐的”。换句话说，每个连通块所包含的顶点编号必须构成一段连续区间。

你可以向图中添加边。求使图变得和谐至少需要添加多少条边。

输入格式

第一行两个整数 n,m (3 <= n <= 200000, 1 <= m <= 200000)。

接下来 m 行，每行两个整数 u,v (1 <= u,v <= n, u != v)，表示一条无向边。保证没有自环和重边。

输出格式

输出使图变得和谐需要添加的最少边数。

样例 1

14 8
1 2
2 7
3 4
6 3
5 7
3 8
6 8
11 12

1

样例 2

200000 3
7 9
9 8
4 5

0