#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 2000
#define M 100000
int max(int a, int b) { return a > b ? a : b; }
int di[] = { -1, 1, 0, 0 };
int dj[] = { 0, 0, -1, 1 };
int *eu[N], *ev[N], eo[N];
void append(int d, int u, int v) {
int o = eo[d]++;
if (o >= 2 && (o & o - 1) == 0) {
eu[d] = (int *) realloc(eu[d], o * 2 * sizeof *eu[d]);
ev[d] = (int *) realloc(ev[d], o * 2 * sizeof *ev[d]);
}
eu[d][o] = u, ev[d][o] = v;
}
int ds[M];
int find(int i) {
return ds[i] < 0 ? i : (ds[i] = find(ds[i]));
}
int join(int i, int j) {
i = find(i);
j = find(j);
if (i == j)
return 0;
if (ds[i] > ds[j])
ds[i] = j;
else {
if (ds[i] == ds[j])
ds[i]--;
ds[j] = i;
}
return 1;
}
int main() {
static int dd[N][N], uu[N][N], qu[N * N];
int n, m, cnt, g, h, i, i_, j, j_, ij, ij_, u, v, d, o, k;
scanf("%d%d", &n, &m);
if (m == 1) {
printf("0\n");
return 0;
}
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
dd[i][j] = n * 2 + 1;
cnt = 0;
for (u = 0; u < m; u++) {
scanf("%d%d", &i, &j), i--, j--;
dd[i][j] = 0, uu[i][j] = u, qu[cnt++] = i * n + j;
}
for (h = 0; h < cnt; h++) {
ij = qu[h], i = ij / n, j = ij % n, d = dd[i][j] + 1, u = uu[i][j];
for (g = 0; g < 4; g++) {
i_ = i + di[g], j_ = j + dj[g], ij_ = i_ * n + j_;
if (i_ >= 0 && i_ < n && j_ >= 0 && j_ < n && dd[i_][j_] > d)
dd[i_][j_] = d, uu[i_][j_] = u, qu[cnt++] = ij_;
}
}
for (d = 0; d < n; d++) {
eu[d] = (int *) malloc(2 * sizeof *eu[d]);
ev[d] = (int *) malloc(2 * sizeof *ev[d]);
}
for (i = 0; i < n; i++)
for (j = 0; j < n; j++) {
u = uu[i][j];
for (g = 0; g < 4; g += 2) {
i_ = i + di[g], j_ = j + dj[g], v = uu[i_][j_];
if (i_ >= 0 && i_ < n && j_ >= 0 && j_ < n && u != v) {
d = max(dd[i][j], dd[i_][j_]);
if (d < n)
append(d, u, v);
}
}
}
memset(ds, -1, m * sizeof *ds);
k = m;
for (d = 0; d < n; d++)
for (o = eo[d]; o--; ) {
u = eu[d][o], v = ev[d][o];
if (join(u, v) && --k == 1) {
printf("%d\n", d);
return 0;
}
}
return 0;
}
