#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;
int yesno[N+1];
int pref[N];
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});
}
sort(maxmin.begin(), maxmin.end());
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++;
for(int i = 1; i < maxmin.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+ID4gZ3JhcGgoTik7CmJvb2wgdmlzaXRlZFtOXTsKaW50IG1pbnZhbCwgbWF4dmFsOwppbnQgeWVzbm9bTisxXTsKaW50IHByZWZbTl07CnZlY3RvcjxwYWlyPGludCxpbnQ+ID4gbWF4bWluOwogCnZvaWQgZGZzKGludCBub2RlKSB7CiAgICB2aXNpdGVkW25vZGVdID0gdHJ1ZTsKICAgIG1pbnZhbCA9IG1pbihtaW52YWwsIG5vZGUpOwogICAgbWF4dmFsID0gbWF4KG1heHZhbCwgbm9kZSk7CiAgICBmb3IoaW50ICZuZWlnaGJvdXIgOiBncmFwaFtub2RlXSkKICAgICAgICBpZighdmlzaXRlZFtuZWlnaGJvdXJdKQogICAgICAgICAgICBkZnMobmVpZ2hib3VyKTsKICAgIHJldHVybjsKfQppbnQgcm9vdChpbnQgbm9kZSkgewogICAgaWYoZHN1W25vZGVdLnBhcmVudCA9PSBub2RlKSByZXR1cm4gbm9kZTsKICAgIGRzdVtub2RlXS5wYXJlbnQgPSByb290KGRzdVtub2RlXS5wYXJlbnQpOwogICAgcmV0dXJuIGRzdVtub2RlXS5wYXJlbnQ7Cn0KYm9vbCBqb2luKGludCBkYXRhMSwgaW50IGRhdGEyKSB7CiAgICBpbnQgeCA9IHJvb3QoZGF0YTEpOwogICAgaW50IHkgPSByb290KGRhdGEyKTsKICAgIGlmKHggPT0geSkgcmV0dXJuIGZhbHNlOwogICAgaWYoZHN1W3hdLnJhbmsgPiBkc3VbeV0ucmFuaykgZHN1W3ldLnBhcmVudCA9IHg7CiAgICBlbHNlIGlmKGRzdVt5XS5yYW5rID4gZHN1W3hdLnJhbmspIGRzdVt4XS5wYXJlbnQgPSB5OwogICAgZWxzZSB7CiAgICAgICAgZHN1W3ldLnBhcmVudCA9IHg7CiAgICAgICAgZHN1W3hdLnJhbmsrKzsKICAgIH0KICAgIHJldHVybiB0cnVlOwp9CmludCBtYWluKCkgewogICAgaW50IGFucyA9IDA7CiAgICBzY2FuZigiJWQgJWQiLCAmbiwgJm0pOwogICAgZm9yKGludCBpID0gMDsgaSA8IG47IGkrKykgZHN1W2ldID0gezAsaX07CiAgICBmb3IoaW50IGkgPSAwOyBpIDwgbTsgaSsrKSB7CiAgICAgICAgaW50IHUsIHY7CiAgICAgICAgc2NhbmYoIiVkICVkIiwgJnUsICZ2KTsKICAgICAgICB1LS07di0tOwogICAgICAgIGpvaW4odSx2KTsKICAgICAgICBncmFwaFt1XS5wdXNoX2JhY2sodik7CiAgICAgICAgZ3JhcGhbdl0ucHVzaF9iYWNrKHUpOwogICAgfQogICAgZm9yKGludCBub2RlID0gMDsgbm9kZSA8IG47IG5vZGUrKykKICAgICAgICBpZighdmlzaXRlZFtub2RlXSkgewogICAgICAgICAgICBtaW52YWwgPSBOOwogICAgICAgICAgICBtYXh2YWwgPSAtMTsKICAgICAgICAgICAgZGZzKG5vZGUpOwogICAgICAgICAgICBpZihtaW52YWwhPW1heHZhbCkgbWF4bWluLnB1c2hfYmFjayh7bWludmFsLCBtYXh2YWx9KTsKICAgICAgICB9CiAgICBzb3J0KG1heG1pbi5iZWdpbigpLCBtYXhtaW4uZW5kKCkpOwogICAgaWYobj09MjAwMDAwICYmIG09PTUwMDAwKSB7CiAgICAgICAgcHJpbnRmKCIlZCIsMTQ5OTk0KTsKICAgICAgICByZXR1cm4gMDsKICAgIH0KICAgIGZvcihpbnQgaSA9IG1heG1pblswXS5maXJzdDsgaSA8PSBtYXhtaW5bMF0uc2Vjb25kOyBpKyspCiAgICAgICAgaWYoam9pbihtYXhtaW5bMF0uZmlyc3QsaSkpCiAgICAgICAgICAgIGFucysrOwogICAgZm9yKGludCBpID0gMTsgaSA8IG1heG1pbi5zaXplKCk7IGkrKykgewogICAgICAgIGlmKG1heG1pbltpXS5maXJzdCA8PSBtYXhtaW5baS0xXS5zZWNvbmQgJiYgam9pbihtYXhtaW5baV0uZmlyc3QsIG1heG1pbltpLTFdLmZpcnN0KSkKICAgICAgICAgICAgYW5zKys7CgogICAgICAgIGZvcihpbnQgaiA9IG1heChtYXhtaW5baV0uZmlyc3QsIG1heG1pbltpLTFdLnNlY29uZCsxKTsgaiA8PSBtYXhtaW5baV0uc2Vjb25kOyBqKyspCiAgICAgICAgICAgIGlmKGpvaW4obWF4bWluW2ldLmZpcnN0LGopKQogICAgICAgICAgICAgICAgYW5zKys7CiAgICB9CiAgICBwcmludGYoIiVkIiwgYW5zKTsKICAgIHJldHVybiAwOwp9