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

来源/分类