1498: 村里有个姑娘叫小Jun

内存限制:128 MB 时间限制:1.000 S
评测方式:文本比较 命题人:
提交:61 解决:15

题目描述

在Jun小镇上有n个村庄,村庄与村庄之间可能直接相连也可能不直接相连,甚至两个村庄就无法相互到达。
现给n个村庄编号为1-n,对所有村庄,若存在村庄l到村庄r的路径(l<r),则有村庄(l+1),(l+2),(l+3)...(r-1)也可到达r,
就可构建和谐小镇。为了达成这一条件,需要添加多少条路径。

输入

第一行两个整数n,m(n为村庄个数,m为直连边数) 3≤n≤200 000 and 1≤m≤200 000
接下来m行,每一行两个整数表示村庄ai和aj直连。

输出

一个整数

样例输入 复制

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

样例输出 复制

1