#include "bits/stdc++.h" using namespace std; #define FOR(i,j,k) for(int (i)=(j);(i)<(int)(k);++(i)) #define rep(i,j) FOR(i,0,j) #define each(x,y) for(auto &(x):(y)) #define mp make_pair #define all(x) (x).begin(),(x).end() #define debug(x) cout<<#x<<": "<<(x)< pii; typedef vector vi; typedef vector vll; class UnionFind{ public: UnionFind(int _n):n(_n), cnt(_n), par(_n), rank(_n), size(_n, 1){ for(int i=0;i par, rank, size; }; const int NAX = 100001, INF = INT_MAX; int N, M, dp[NAX]; int main(){ while(cin >> N >> M){ UnionFind uf(N + 1); rep(i, M){ int u, v; scanf("%d%d", &u, &v); uf.unite(u, v); } vi cc(N + 1), w, cnt; FOR(i, 1, N + 1)cc[uf[i]]++; map cnt_; FOR(i, 1, N + 1)if(cc[i])cnt_[cc[i]]++; each(p, cnt_)w.push_back(p.first), cnt.push_back(p.second); rep(j, N + 1)dp[j] = INF; dp[0] = -1; rep(i, sz(w)){ int nw; for(int j = N; j >= 0; --j) for(int m = 1; (nw = j - m*w[i]) >= 0 && m <= cnt[i]; ++m) if(dp[nw] != INF)smin(dp[j], dp[nw] + m); } FOR(i, 1, N + 1)printf("%d\n", dp[i] != INF ? dp[i] : -1); } }