#include<stdio.h>
#include<stdlib.h>#define N 1100
int c[N];
int main() {
int l,n,i,m,a,b,front[N],tail[N];
while(scanf("%d%d",&l,&n)!=EOF) {
for(i=0;i<=l;i++)
c[i]=999999;
for(i=0;i<n;i++) {
scanf("%d%d",&a,&b);
c[a]=b;
}
front[0]=1;
a=1;
for(i=1;i<=l;i++) {
a++;
if(c[i]<a)
a=c[i];
front[i]=a;
}
b=999999;
tail[l]=999999;
for(i=l-1;i>=0;i--) {
b++;
if(c[i]<b)
b=c[i];
tail[i]=b;
}
for(i=0;i<=l;i++)
if(front[i]>tail[i])
front[i]=tail[i];
m=-999999;
for(i=0;i<=l;i++)
if(m<front[i])
m=front[i];
printf("%d ",m);
}
return 0;
}