#include <bits/stdc++.h>
using namespace std;
const int inf = 2e3 + 9;
const int dx[4] = {-1, 1, 0, 0};
const int dy[4] = {0, 0, -1, 1};
struct state {
int dist, y, x;
};
struct ds {
int par[inf * inf], siz[inf * inf];
inline int find(int u) {
if (u == par[u]) return u;
return par[u] = find(par[u]);
}
inline void merge(int u, int v) {
u = find(u); v = find(v);
if (u == v) return;
par[u] = v;
siz[v] += siz[u];
siz[u] = 0;
}
} cul;
int n, m;
int vis[inf][inf];
int main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n >> m;
for (int i = 0; i < n * n; ++i) cul.par[i] = i;
memset(vis, -1, sizeof(vis));
queue<state> q;
for (int i = 0; i < m; i++) {
int x, y; cin >> x >> y;
cul.siz[--y * n + --x] = 1;
q.push({0, y, x});
vis[y][x] = y * n + x;
}
while (!q.empty()) {
state s = q.front();
int dist = s.dist;
int y = s.y, x = s.x;
int here = y * n + x;
q.pop();
cul.merge(here, vis[y][x]);
for (int i = 0; i < 4; ++i) {
int ny = y + dy[i], nx = x + dx[i];
if (ny < 0 || ny >= n || nx < 0 || nx >= n) continue;
int there = ny * n + nx;
if (cul.siz[cul.find(there)] && cul.siz[cul.find(here)]) cul.merge(there, here);
if (vis[ny][nx] == -1) {
q.push({dist + 1, ny, nx});
vis[ny][nx] = here;
}
}
if (cul.siz[cul.find(here)] == m) {
cout << dist << '\n';
break;
}
}
}
