#include <bits/stdc++.h>
using namespace std;
struct point{
int x,y;
};
int N,K,cnt;
int A[2001][2001],Par[100001],dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};
point Point[100001];
queue<point> Q;
int getpar(int v){
if (v==Par[v])
return v;
return Par[v]=getpar(Par[v]);
}
void unite(int a,int b){
a=getpar(a);
b=getpar(b);
if (a!=b){
Par[b]=a;
cnt--;
}
}
bool f(int x,int y){
return 0<x&&x<=N&&0<y&&y<=N;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>N>>K;
cnt=K;
for (int i=1; i<=K; i++){
cin>>Point[i].x>>Point[i].y;
A[Point[i].x][Point[i].y]=i;
Q.push({Point[i].x,Point[i].y});
Par[i]=i;
}
for (int ans=0;;ans++){
int sz=Q.size();
while (sz--){
point t=Q.front();
Q.pop();
for (int i=0; i<4; i++){
int x=t.x+dx[i],y=t.y+dy[i];
if (f(x,y)&&A[x][y]){
unite(A[t.x][t.y],A[x][y]);
if (cnt==1){
cout<<ans;
return 0;
}
}
}
Q.push(t);
}
sz=Q.size();
while (sz--){
point t=Q.front();
Q.pop();
for (int i=0; i<4; i++){
int x=t.x+dx[i],y=t.y+dy[i];
if (f(x,y)&&!A[x][y]){
A[x][y]=A[t.x][t.y];
Q.push({x,y});
}
}
}
}
}
