#include <stdio.h>
#include <stdlib.h>
#define M 200000
#define N (M * 2)
int min(int a, int b) { return a < b ? a : b; }
int max(int a, int b) { return a > b ? a : b; }
unsigned int Z = 12345;
int rand_() {
return (Z *= 3) >> 1;
}
int xx[M * 2], ij[M * 2], m;
void sort(int *hh, int l, int r) {
while (l < r) {
int i = l, j = l, k = r, h = hh[l + rand_() % (r - l)], tmp;
while (j < k)
if (xx[hh[j]] == xx[h])
j++;
else if (xx[hh[j]] < xx[h]) {
tmp = hh[i], hh[i] = hh[j], hh[j] = tmp;
i++, j++;
} else {
k--;
tmp = hh[j], hh[j] = hh[k], hh[k] = tmp;
}
sort(hh, l, i);
l = k;
}
}
int *ej[N * 2], eo[N * 2], 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 qu[N * 2], ans;
void dfs(int i, int d) {
int o;
qu[d] = i;
if (i < n) {
ans = min(ans, d + 1);
while (ans > 0 && qu[d - (ans - 1)] - i >= n)
ans--;
}
for (o = eo[i]; o--; ) {
int j = ej[i][o];
dfs(j, d + 1);
}
}
int main() {
static int hh[M * 2], jj[N];
int h, i, j;
scanf("%d%*d", &m);
for (h = 0; h < m * 2; h++)
scanf("%d", &xx[h]);
for (h = 0; h < m * 2; h++)
hh[h] = h;
sort(hh, 0, m * 2);
n = 0;
for (h = 0; h < m * 2; h++)
ij[hh[h]] = h + 1 == m * 2 || xx[hh[h + 1]] != xx[hh[h]] ? n++ : n;
for (i = 0; i < n; i++)
jj[i] = i;
for (h = 0; h < m; h++) {
i = ij[h << 1 | 0], j = ij[h << 1 | 1];
if (i < j)
jj[i] = max(jj[i], j);
else
jj[0] = max(jj[0], j), jj[i] = max(jj[i], n + j);
}
for (i = 1; i < n; i++)
jj[i] = max(jj[i], jj[i - 1]);
for (i = 0; i < n; i++)
if (jj[i] == i) {
printf("-1\n");
return 0;
}
for (i = 0; i < n * 2; i++)
ej[i] = (int *) malloc(2 * sizeof *ej[i]);
for (i = 0; i < n; i++) {
append(jj[i], i);
if (jj[i] < n)
append(n + jj[i], n + i);
}
ans = m;
for (i = 0; i < n; i++)
if (jj[i] >= n)
dfs(n + i, 0);
printf("%d\n", ans);
return 0;
}
