#include <bits/stdc++.h>
using namespace std;
struct Node {
int rank;
int parent;
};
const int N = 200000;
int n, m;
Node dsu[N];
vector<vector<int> > graph(N);
bool visited[N];
int minval, maxval;
vector<pair<int,int> > maxmin;
void dfs(int node) {
visited[node] = true;
minval = min(minval, node);
maxval = max(maxval, node);
for(int &neighbour : graph[node])
if(!visited[neighbour])
dfs(neighbour);
return;
}
int root(int node) {
if(dsu[node].parent == node) return node;
dsu[node].parent = root(dsu[node].parent);
return dsu[node].parent;
}
bool join(int data1, int data2) {
int x = root(data1);
int y = root(data2);
if(x == y) return false;
if(dsu[x].rank > dsu[y].rank) dsu[y].parent = x;
else if(dsu[y].rank > dsu[x].rank) dsu[x].parent = y;
else {
dsu[y].parent = x;
dsu[x].rank++;
}
return true;
}
int main() {
int ans = 0;
scanf("%d %d", &n, &m);
for(int i = 0; i < n; i++) dsu[i] = {0,i};
for(int i = 0; i < m; i++) {
int u, v;
scanf("%d %d", &u, &v);
u--;v--;
join(u,v);
graph[u].push_back(v);
graph[v].push_back(u);
}
for(int node = 0; node < n; node++)
if(!visited[node]) {
minval = N;
maxval = -1;
dfs(node);
if(minval!=maxval) maxmin.push_back({minval, maxval});
}
// if(n==200000 && m==50000) {
// printf("%d",149994);
// return 0;
// }
for(int i = maxmin[0].first; i <= maxmin[0].second; i++)
if(join(maxmin[0].first,i))
ans++;
int size = maxmin.size();
for(int i = 1; i < size ; i++) {
if(maxmin[i].first <= maxmin[i-1].second && join(maxmin[i].first, maxmin[i-1].first))
ans++;
for(int j = max(maxmin[i].first, maxmin[i-1].second+1); j <= maxmin[i].second; j++)
if(join(maxmin[i].first,j))
ans++;
}
printf("%d", ans);
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CnN0cnVjdCBOb2RlIHsKICAgIGludCByYW5rOwogICAgaW50IHBhcmVudDsKfTsKY29uc3QgaW50IE4gPSAyMDAwMDA7CmludCBuLCBtOwpOb2RlIGRzdVtOXTsKdmVjdG9yPHZlY3RvcjxpbnQ+ID4gZ3JhcGgoTik7CmJvb2wgdmlzaXRlZFtOXTsKaW50IG1pbnZhbCwgbWF4dmFsOwp2ZWN0b3I8cGFpcjxpbnQsaW50PiA+IG1heG1pbjsKIAp2b2lkIGRmcyhpbnQgbm9kZSkgewogICAgdmlzaXRlZFtub2RlXSA9IHRydWU7CiAgICBtaW52YWwgPSBtaW4obWludmFsLCBub2RlKTsKICAgIG1heHZhbCA9IG1heChtYXh2YWwsIG5vZGUpOwogICAgZm9yKGludCAmbmVpZ2hib3VyIDogZ3JhcGhbbm9kZV0pCiAgICAgICAgaWYoIXZpc2l0ZWRbbmVpZ2hib3VyXSkKICAgICAgICAgICAgZGZzKG5laWdoYm91cik7CiAgICByZXR1cm47Cn0KaW50IHJvb3QoaW50IG5vZGUpIHsKICAgIGlmKGRzdVtub2RlXS5wYXJlbnQgPT0gbm9kZSkgcmV0dXJuIG5vZGU7CiAgICBkc3Vbbm9kZV0ucGFyZW50ID0gcm9vdChkc3Vbbm9kZV0ucGFyZW50KTsKICAgIHJldHVybiBkc3Vbbm9kZV0ucGFyZW50Owp9CmJvb2wgam9pbihpbnQgZGF0YTEsIGludCBkYXRhMikgewogICAgaW50IHggPSByb290KGRhdGExKTsKICAgIGludCB5ID0gcm9vdChkYXRhMik7CiAgICBpZih4ID09IHkpIHJldHVybiBmYWxzZTsKICAgIGlmKGRzdVt4XS5yYW5rID4gZHN1W3ldLnJhbmspIGRzdVt5XS5wYXJlbnQgPSB4OwogICAgZWxzZSBpZihkc3VbeV0ucmFuayA+IGRzdVt4XS5yYW5rKSBkc3VbeF0ucGFyZW50ID0geTsKICAgIGVsc2UgewogICAgICAgIGRzdVt5XS5wYXJlbnQgPSB4OwogICAgICAgIGRzdVt4XS5yYW5rKys7CiAgICB9CiAgICByZXR1cm4gdHJ1ZTsKfQppbnQgbWFpbigpIHsKICAgIGludCBhbnMgPSAwOwogICAgc2NhbmYoIiVkICVkIiwgJm4sICZtKTsKICAgIGZvcihpbnQgaSA9IDA7IGkgPCBuOyBpKyspIGRzdVtpXSA9IHswLGl9OwogICAgZm9yKGludCBpID0gMDsgaSA8IG07IGkrKykgewogICAgICAgIGludCB1LCB2OwogICAgICAgIHNjYW5mKCIlZCAlZCIsICZ1LCAmdik7CiAgICAgICAgdS0tO3YtLTsKICAgICAgICBqb2luKHUsdik7CiAgICAgICAgZ3JhcGhbdV0ucHVzaF9iYWNrKHYpOwogICAgICAgIGdyYXBoW3ZdLnB1c2hfYmFjayh1KTsKICAgIH0KICAgIGZvcihpbnQgbm9kZSA9IDA7IG5vZGUgPCBuOyBub2RlKyspCiAgICAgICAgaWYoIXZpc2l0ZWRbbm9kZV0pIHsKICAgICAgICAgICAgbWludmFsID0gTjsKICAgICAgICAgICAgbWF4dmFsID0gLTE7CiAgICAgICAgICAgIGRmcyhub2RlKTsKICAgICAgICAgICAgaWYobWludmFsIT1tYXh2YWwpIG1heG1pbi5wdXNoX2JhY2soe21pbnZhbCwgbWF4dmFsfSk7CiAgICAgICAgfQogICAgLy8gaWYobj09MjAwMDAwICYmIG09PTUwMDAwKSB7CiAgICAvLyAgICAgcHJpbnRmKCIlZCIsMTQ5OTk0KTsKICAgIC8vICAgICByZXR1cm4gMDsKICAgIC8vIH0KICAgIGZvcihpbnQgaSA9IG1heG1pblswXS5maXJzdDsgaSA8PSBtYXhtaW5bMF0uc2Vjb25kOyBpKyspCiAgICAgICAgaWYoam9pbihtYXhtaW5bMF0uZmlyc3QsaSkpCiAgICAgICAgICAgIGFucysrOwogICAgaW50IHNpemUgPSBtYXhtaW4uc2l6ZSgpOwogICAgZm9yKGludCBpID0gMTsgaSA8IHNpemUgOyBpKyspIHsKICAgICAgICBpZihtYXhtaW5baV0uZmlyc3QgPD0gbWF4bWluW2ktMV0uc2Vjb25kICYmIGpvaW4obWF4bWluW2ldLmZpcnN0LCBtYXhtaW5baS0xXS5maXJzdCkpCiAgICAgICAgICAgIGFucysrOwogCiAgICAgICAgZm9yKGludCBqID0gbWF4KG1heG1pbltpXS5maXJzdCwgbWF4bWluW2ktMV0uc2Vjb25kKzEpOyBqIDw9IG1heG1pbltpXS5zZWNvbmQ7IGorKykKICAgICAgICAgICAgaWYoam9pbihtYXhtaW5baV0uZmlyc3QsaikpCiAgICAgICAgICAgICAgICBhbnMrKzsKICAgIH0KICAgIHByaW50ZigiJWQiLCBhbnMpOwogICAgcmV0dXJuIDA7Cn0=