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个村庄编号为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直连。
接下来m行,每一行两个整数表示村庄ai和aj直连。
输出
一个整数
样例输入 复制
14 8
1 2
2 7
3 4
6 3
5 7
3 8
6 8
11 12
样例输出 复制
1