#include <bits/stdc++.h>
using namespace std;
int B[200005];
vector<int> adj[200005];
struct SegTree {
vector<int> seg;
int MAX;
SegTree(int N) {
int i;
for(i=1;i<2*N;i*=2) {}
seg.resize(i);
MAX = i;
for(i=0;i<MAX;i++) seg[i] = -1e9;
}
void add(int s, int e, int k, int n, int ns, int ne) {
if(e<=ns||ne<=s) return;
if(s<=ns&&ne<=e) {
seg[n] = max(seg[n], k);
return;
}
int mid = ns + ne >> 1;
add(s, e, k, 2*n, ns, mid);
add(s, e, k, 2*n+1, mid, ne);
}
int get_val(int n) {
n += MAX/2;
int v = seg[n];
while(n != 0) {
v = max(v, seg[n]);
n /= 2;
}
return v;
}
};
set<int> S;
signed main() {
cin.sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int N, M;
cin >> N >> M;
int i, j;
for(i=1;i<=N;i++) B[i] = i;
for(i=0;i<M;i++) {
int a, b;
cin >> a >> b;
if(a > b) swap(a, b);
B[a] = max(B[a], b);
adj[a].push_back(b);
}
SegTree tree(N+3);
int MAX = tree.MAX;
tree.add(1, 2, 0, 1, 0, MAX/2);
int ma = 1;
for(i=1;i<=N;i++) {
ma = max(ma, B[i]);
int v = tree.get_val(i);
S.erase(i);
for(int n : adj[i]) {
S.insert(n);
}
//cout << v << ' ' << S.size() << '\n';
//cout << i << " : " << ma << ' ' << v + (int)S.size() << '\n';
tree.add(ma, N+1, v + (int)S.size(), 1, 0, MAX/2);
}
cout << N-1 - tree.get_val(N);
}
