#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], c[N][N];
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};
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) {
int t1, t2;
if (g[x][y] == -1) return;
if (g[x][y] == 0) {
qx.push(x);
qy.push(y);
qg.push(fg);
qc.push(fc + 1);
g[x][y] = fg;
c[x][y] = fc + 1;
return;
}
t1 = uni(g[x][y]);
t2 = uni(fg);
if (t1 != t2) {
ca[t2] = t1;
ans = max(ans, max(c[x][y], fc));
k--;
if (k == 1) {
cout << ans << endl;
exit(0);
}
}
}
int main()
{
int i, j, fx, fy, fg, fc;
cin >> n >> k;
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();
for (i = 0; i < 4; i++) {
f(fx + dx[i], fy + dy[i], fg, fc);
}
}
return 0;
}
