#include <stdio.h>
#include <stdlib.h>
#define N 200000
int max(int a, int b) { return a > b ? a : b; }
int *ej[N], eo[N];
void append(int i, int j) {
int o = eo[i]++;
if (o >= 2 && (o & o - 1) == 0)
ej[i] = (int *) realloc(ej[i], o * 2 * sizeof *ej[i]);
ej[i][o] = j;
}
int main() {
static char used[N];
static int jj[N], kk[N], dp[N + 1], dq[N + 1];
int n, m, h, i, j, j_, k, o, tmp;
scanf("%d%d", &n, &m);
for (i = 0; i < n; i++)
ej[i] = (int *) malloc(2 * sizeof *ej[i]);
for (h = 0; h < m; h++) {
scanf("%d%d", &i, &j), i--, j--;
if (i > j)
tmp = i, i = j, j = tmp;
append(i, j);
}
for (i = 0, j_ = -1, k = 0; i < n; i++) {
if (used[i])
k--;
j_ = max(j_, i + 1);
for (o = eo[i]; o--; ) {
j = ej[i][o];
if (!used[j])
used[j] = 1, k++;
j_ = max(j_, j);
}
jj[i] = j_, kk[i] = k;
}
dp[n - 1] = dq[n - 1] = 0;
for (i = n - 2; i >= 0; i--) {
dp[i] = kk[i] + dq[jj[i]];
dq[i] = max(dq[i + 1], dp[i]);
}
printf("%d\n", n - 1 - dp[0]);
return 0;
}
