#include <iostream>
#include <utility>
#include <queue>
using namespace std;
typedef pair<int,int> P;
#define x first
#define y second
P t;
queue<P> q;
int table[2010][2010],ans=0,cnt,n,k;
int parent[100010];
int par(int a)
{
if(parent[a]==a) return a;
return parent[a]=par(parent[a]);
}
void uni(int a, int b)
{
if(par(a)!=par(b))
{
parent[par(a)]=par(b);
cnt--;
}
}
bool ch(int a, int b)
{
if(a<1||b<1||a>n||b>n) return 0;
return 1;
}
void view(int a, int b)
{
if(table[a-1][b]) uni(table[a-1][b],table[a][b]);
if(table[a+1][b]) uni(table[a+1][b],table[a][b]);
if(table[a][b+1]) uni(table[a][b+1],table[a][b]);
if(table[a][b-1]) uni(table[a][b-1],table[a][b]);
}
int main()
{
int i, j,a,b,si;
ios_base::sync_with_stdio(false);
cin.tie(0);
cin>>n>>k;
for(i=1;i<=k;i++)
{
cin>>a>>b;
table[a][b]=i;
parent[i]=i;
cnt++;
if(table[a-1][b]) uni(table[a-1][b],table[a][b]);
if(table[a+1][b]) uni(table[a+1][b],table[a][b]);
if(table[a][b+1]) uni(table[a][b+1],table[a][b]);
if(table[a][b-1]) uni(table[a][b-1],table[a][b]);
q.push({a,b});
}
if(cnt==1)
{
cout<<0;
return 0;
}
while(!q.empty())
{
ans++;
si=q.size();
for(i=1;i<=si;i++) {
a=q.front().x;
b=q.front().y;
q.pop();
if(table[a+1][b]==0&&ch(a+1,b)){table[a+1][b]=par(table[a][b]);q.push({a+1,b});view(a+1,b);}
if(table[a-1][b]==0&&ch(a-1,b)){table[a-1][b]=par(table[a][b]);q.push({a-1,b});view(a-1,b);}
if(table[a][b+1]==0&&ch(a,b+1)){table[a][b+1]=par(table[a][b]);q.push({a,b+1});view(a,b+1);}
if(table[a][b-1]==0&&ch(a,b-1)){table[a][b-1]=par(table[a][b]);q.push({a,b-1});view(a,b-1);}
}
if(cnt==1)
{
cout<<ans;
return 0;
}
}
}
