#include<bits/stdc++.h>
#define ll long long
ll read(){
	ll x=1,y=0;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-') x=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		y=(y<<1)+(y<<3)+(c^48);
		c=getchar();
	}
	return x*y;
}
void write(ll x){
	if(x<0) putchar('-'),x=-x;
	if(x>9){
		write(x/10);
	}
	putchar(x%10+'0');
}
using namespace std;
const int N=400010;

ll n1,m1;
ll n,m;
ll d[N],f[N],ans;
ll q[N],l,r;
ll fa[N],siz[N];
ll num[N];

ll fnd(ll x){
	if(fa[x]==x) return x;
	return fa[x]=fnd(fa[x]);
}

int main(){
    cin>>n1>>m1;
    for(int i=1;i<=n1;i++) fa[i]=i,siz[i]=1;
    for(int i=1;i<=m1;i++){
    	ll x,y;
    	cin>>x>>y;
    	ll fx=fnd(x),fy=fnd(y);
    	if(fx!=fy){
    		fa[fy]=fx;
    		siz[fx]+=siz[fy];
    		siz[fy]=0;
    	}
    }
    for(int i=1;i<=n1;i++){
    	if(siz[i]>0){
    		num[siz[i]]++;
    	}
    }
    
    n=sqrt(n);m=n1;
    for(int i=1;i<=m;i++) d[i]=-0x3f3f3f3f3f3f3f3f;
    for(int i=1;i<=n;i++){
        ll x,y,z;
        y=i;z=-1;x=num[i];
        // cin>>y>>z>>x;
//         memset(f,0,sizeof(f));
        for(int j=1;j<=m*2;j++){
            f[j]=-0x3f3f3f3f3f3f3f;
        }
        f[0]=0;
        for(int j=0;j<y;j++){
            ll w=(m-j)/y+1;
            l=1;r=0;
            for(int k=0;k<=w&&k*y+j<=m;k++){
                // if(k*y+j==0) continue;
                ll u=k*y+j;
                while(l<=r&&k-q[l]>x) l++;
                
                if(l<=r){
                    f[u]=max(f[u],d[q[l]*y+j]-q[l]*z+k*z);
                }
                
                while(l<=r&&d[q[r]*y+j]-q[r]*z<=d[u]-k*z) r--;
                
                q[++r]=k;
            }
        }
        for(int j=1;j<=m;j++){
            d[j]=max(d[j],f[j]);
//            f[j]=-0x3f3f3f3f3f3f3f3f;
            // cout<<f[j]<<" ";
        }
        // cout<<endl;
    }
    for(int i=1;i<=m;i++){
        if(d[i]<-2*n) cout<<-1<<endl;
    	else cout<<-d[i]-1<<endl;
    }
    return 0;
}