#include <stdio.h>
#include <queue>
#include <vector>
#include <functional>
#include <algorithm>
#define max2(x,y) (x>y?x:y)
using namespace std;
typedef pair<int,pair<int,int> > pip;
int n, m, p[100001], max_t;
int dy[4]={1,-1,0,0}, dx[4]={0,0,1,-1};
pair<int,int> board[2001][2001];
queue<int> Q;
priority_queue<pip,vector<pip>,greater<pip> > Q2;
int get_p(int x){
if(p[x]==x) return x;
return p[x]=get_p(p[x]);
}
int main(){
int x, y, xx, yy, tx, ty;
scanf("%d %d",&n,&m);
for(int i=1; i<=m; i++){
scanf("%d %d",&x,&y);
board[x][y]={i,0}, p[i]=i;
Q.push(x), Q.push(y);
}
while(!Q.empty()){
xx=Q.front(), Q.pop();
yy=Q.front(), Q.pop();
while(Q2.empty()==false && Q2.top().first<=board[xx][yy].second){
int px=get_p(Q2.top().second.first);
int py=get_p(Q2.top().second.second);
if(px!=py) p[px]=py, max_t=max2(max_t,Q2.top().first);
Q2.pop();
}
for(int i=0; i<4; i++){
tx=xx+dx[i], ty=yy+dy[i];
if(1<=tx && tx<=n && 1<=ty && ty<=n){
if(board[tx][ty].first==0){
board[tx][ty]={board[xx][yy].first,board[xx][yy].second+1};
Q.push(tx), Q.push(ty);
}
int px=get_p(board[tx][ty].first);
int py=get_p(board[xx][yy].first);
if(px!=py) Q2.push({board[tx][ty].second,{px,py}});
}
}
}
while(!Q2.empty()){
int px=get_p(Q2.top().second.first);
int py=get_p(Q2.top().second.second);
if(px!=py) p[px]=py, max_t=max2(max_t,Q2.top().first);
Q2.pop();
} printf("%d",max_t);
}
