#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
#define N 2005
#define K 100005
using namespace std;
int n, k, ans, ca[K], g[N][N];
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};
bool v[N][N];
queue<int> qx, qy, qg, qc;
int uni(int p) {
if (ca[p] == p) return p;
return ca[p] = uni(ca[p]);
}
void f(int x, int y, int fg, int fc) {
if (g[x][y] == -1) return;
if (v[x][y] == 0) {
qx.push(x);
qy.push(y);
qg.push(fg);
qc.push(fc + 1);
v[x][y] = 1;
return;
}
}
int main()
{
int i, j, t1, t2, fx, fy, fg, fc;
cin >> n >> k;
if (k == 1) {cout << '0' << endl; return 0;}
for (i = 1; i <= k; i++) ca[i] = i;
for (i = 0; i <= n + 1; i++) for (j = 0; j <= n + 1; j++) g[i][j] = -1;
for (i = 1; i <= n; i++) for (j = 1; j <= n; j++) g[i][j] = 0;
for (i = 1; i <= k; i++) {
scanf("%d %d", &fx, &fy);
qx.push(fx);
qy.push(fy);
qg.push(i);
qc.push(0);
g[fx][fy] = i;
}
while (!qx.empty()) {
fx = qx.front(), qx.pop();
fy = qy.front(), qy.pop();
fg = qg.front(), qg.pop();
fc = qc.front(), qc.pop();
g[fx][fy] = fg;
for (i = 0; i < 4; i++) {
if (g[fx + dx[i]][fy + dy[i]] > 0) {
t1 = uni(g[fx + dx[i]][fy + dy[i]]);
t2 = uni(fg);
if (t1 != t2) {
ca[t2] = t1;
ans = fc;
}
}
}
for (i = 0; i < 4; i++) {
f(fx + dx[i], fy + dy[i], fg, fc);
}
}
cout << ans << endl;
return 0;
}
