#include<bits/stdc++.h>
#define maxn 200010
using namespace std;
int n,m,a[maxn],b[maxn],f[maxn];
int solve(int z){
	memset(f,0,sizeof(f));
	for(int i=1;i<=m;i++){
		if(b[i]-a[i]>z&&n-(b[i]-a[i])>z)return 0;
		else if(b[i]-a[i]<=z&&n-(b[i]-a[i])>z){
			f[a[i]]++,f[b[i]]--;
		}
		else if(b[i]-a[i]>z&&n-(b[i]-a[i])<=z){
			f[1]++,f[a[i]]--;
			f[b[i]]++,f[n+1]--;
		}
	}
	for(int i=1;i<=n;i++)f[i]+=f[i-1];
	for(int i=1;i<=n;i++)cout<<f[i]<<" ";cout<<endl;
	for(int i=1;i<=n;i++)if(f[i]==0)return 1; 
	return 0;
}
int main() {
	//freopen("F.in", "r", stdin); 
    while(~scanf("%d%d",&n,&m)){
	    for(int i=1;i<=m;i++)scanf("%d%d",&a[i],&b[i]);
	    for(int i=1;i<=m;i++)if(a[i]>b[i])swap(a[i],b[i]);
		int l=0,r=n-1,mid,ans=n-1;
		while(l<=r){
			int mid=(l+r)>>1;cout<<mid<<" "<<l<<" "<<r<<endl;
			if(solve(mid))ans=mid,r=mid-1;
			else l=mid+1;
		}	
		printf("%d\n",ans);
	}
	return 0;
}