#include <bits/stdc++.h>
using namespace std;
int ans=0,n;
vector <vector <int> > dis(1000,vector <int>(1000,0));
vector <vector <int> > check(1000,vector <int>(1000,0));
const int dx[]={1,0,-1,0},dy[]={0,1,0,-1};
bool checke(int x,int y){
if (x<n && x>=0 && y<n && y>=0) return true;
return false;
}
int main(){
int s;cin >> n >> s;
queue<pair<int,int> > q;
while(s--){
int x,y;cin >> x >> y;
q.push(make_pair(x,y));
check[x][y]=1;
}
while(!q.empty()){
int x=q.front().first,y=q.front().second;q.pop();
ans=max(ans,dis[x][y]);
for(int i=0;i<4;i++){
if(checke(x+dx[i],y+dy[i]) && !check[x+dx[i]][y+dy[i]]){
q.push(make_pair(x+dx[i],y+dy[i]));
check[x+dx[i]][y+dy[i]]=1;
dis[x+dx[i]][y+dy[i]]=dis[x][y]+1;
}
}
/*for(int j=0;j<n;j++){
for(int i=0;i<n;i++){
cout << dis[i][j] << " ";
}
cout << endl;
}
cout << endl;*/
}
cout << ans << endl;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CmludCBhbnM9MCxuOwp2ZWN0b3IgPHZlY3RvciA8aW50PiA+IGRpcygxMDAwLHZlY3RvciA8aW50PigxMDAwLDApKTsKdmVjdG9yIDx2ZWN0b3IgPGludD4gPiBjaGVjaygxMDAwLHZlY3RvciA8aW50PigxMDAwLDApKTsKY29uc3QgaW50IGR4W109ezEsMCwtMSwwfSxkeVtdPXswLDEsMCwtMX07CmJvb2wgY2hlY2tlKGludCB4LGludCB5KXsKICAgIGlmICh4PG4gJiYgeD49MCAmJiB5PG4gJiYgeT49MCkgcmV0dXJuIHRydWU7CiAgICByZXR1cm4gZmFsc2U7Cn0KaW50IG1haW4oKXsKICAgaW50IHM7Y2luID4+IG4gPj4gczsKICAgcXVldWU8cGFpcjxpbnQsaW50PiA+IHE7CiAgIHdoaWxlKHMtLSl7CiAgICAgIGludCB4LHk7Y2luID4+IHggPj4geTsKICAgICAgcS5wdXNoKG1ha2VfcGFpcih4LHkpKTsKICAgICAgY2hlY2tbeF1beV09MTsKICAgfQogICB3aGlsZSghcS5lbXB0eSgpKXsKICAgICAgaW50IHg9cS5mcm9udCgpLmZpcnN0LHk9cS5mcm9udCgpLnNlY29uZDtxLnBvcCgpOwogICAgICBhbnM9bWF4KGFucyxkaXNbeF1beV0pOwogICAgICBmb3IoaW50IGk9MDtpPDQ7aSsrKXsKICAgICAgICAgaWYoY2hlY2tlKHgrZHhbaV0seStkeVtpXSkgJiYgIWNoZWNrW3grZHhbaV1dW3krZHlbaV1dKXsKICAgICAgICAgICAgcS5wdXNoKG1ha2VfcGFpcih4K2R4W2ldLHkrZHlbaV0pKTsKICAgICAgICAgICAgY2hlY2tbeCtkeFtpXV1beStkeVtpXV09MTsKICAgICAgICAgICAgZGlzW3grZHhbaV1dW3krZHlbaV1dPWRpc1t4XVt5XSsxOwogICAgICAgICB9CiAgICAgIH0KICAgICAgLypmb3IoaW50IGo9MDtqPG47aisrKXsKICAgICAgCWZvcihpbnQgaT0wO2k8bjtpKyspewogICAgICAJCWNvdXQgPDwgZGlzW2ldW2pdIDw8ICIgIjsKICAgICAgCX0KICAgICAgCWNvdXQgPDwgZW5kbDsKICAgICAgfQogICAgICBjb3V0IDw8IGVuZGw7Ki8KICAgfQogICBjb3V0IDw8IGFucyA8PCBlbmRsOwp9