#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,par[101010],sz[101010],chk[2020][2020],day[2020][2020],dx[4]={0,0,1,-1},dy[4]={-1,1,0,0},cnt,a,b;
queue<int> qx,qy;
int f(int a){
if(a==par[a]) return a;
return par[a]=f(par[a]);
}
void uni(int a,int b){
if(sz[a]>=sz[b]) par[b]=a,sz[a]+=sz[b];
else par[a]=b,sz[b]+=sz[a];
}
main(){
cin >> n >> m;
for(int i=1;i<=m;i++){
cin >> a >> b;
par[i]=chk[a][b]=i;
qx.push(a),qy.push(b);
}
if(m==1){cout << 0;return 0;}
while(!qx.empty()){
int x=qx.front(),y=qy.front();
qx.pop(),qy.pop();
for(int i=0;i<4;i++){
int xx=x+dx[i],yy=y+dy[i];
if(xx<1 || yy<1 || xx>n || yy>n) continue;
if(chk[xx][yy]){
if(day[xx][yy] <= day[x][y] && f(chk[x][y]) != f(chk[xx][yy])){
uni(f(chk[x][y]),f(chk[xx][yy]));
cnt++;
if(cnt == m-1){cout << day[x][y];return 0;}
}
continue;
}
qx.push(xx),qy.push(yy);
chk[xx][yy]=chk[x][y];
day[xx][yy]=day[x][y]+1;
}
}
}
