#include using namespace std; /*^ debug */ template string to_string(pair p); template string to_string(tuple p); template string to_string(tuple p); string to_string(const string& s) { return '"' + s + '"'; } string to_string(const char* s) { return to_string((string) s); } string to_string(bool b) { return (b ? "true" : "false"); } string to_string(vector v) { bool first = true; string res = "{"; for (int i = 0; i < static_cast(v.size()); i++) { if (!first) { res += ", "; } first = false; res += to_string(v[i]); } res += "}"; return res; } template string to_string(bitset v) { string res = ""; for (size_t i = 0; i < N; i++) { res += static_cast('0' + v[i]); } return res; } template string to_string(A v) { bool first = true; string res = "{"; for (const auto &x : v) { if (!first) { res += ", "; } first = false; res += to_string(x); } res += "}"; return res; } template string to_string(pair p) { return "(" + to_string(p.first) + ", " + to_string(p.second) + ")"; } template string to_string(tuple p) { return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ")"; } template string to_string(tuple p) { return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")"; } void debug_out() { cerr << endl; } template void debug_out(Head H, Tail... T) { cerr << " " << to_string(H); debug_out(T...); } #ifdef LOCAL #define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__) #else #define debug(...) 42 #endif /* debug $*/ /*^ vector extensions */ template T concat(initializer_list lists) { T a; for (auto &l : lists) a.insert(a.end(), l.begin(), l.end()); return a; } template struct _Matrix_type { typedef vector::type> type; }; template struct _Matrix_type { typedef T type; }; template struct _Matrix { static auto build(size_t s) { return vector(s); } template static auto build(size_t f, Args... args) { return vector::type>(f, _Matrix::build(args...)); } }; template auto buildMatrix(Args... args) { return _Matrix::build(args...); } /* vector extensions $*/ /*^ generic definitions */ template struct _RecurFun : F { _RecurFun(F&& f) : F(forward(f)) {} template decltype(auto) operator()(Args&&... args) const { return F::operator()(*this, forward(args)...); } }; template decltype(auto) RecurFun(F&& f) { return _RecurFun { forward(f) }; } /* generic definitions $*/ struct DSU { vector fa; vector sz; DSU(int n) : fa(n), sz(n, 1) { iota(fa.begin(), fa.end(), 0); } int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); } bool unite(int x, int y) { int fx = find(x); int fy = find(y); if (fx == fy) return false; fa[fy] = fx; sz[fx] += sz[fy]; return true; } }; int main() { ios::sync_with_stdio(false); int N, M; { cin >> N >> M; } DSU dsu(N); { for (int i = 0; i < M; ++i) { int U, V; { cin >> U >> V; --U, --V; } dsu.unite(U, V); } } map ccsize2cnt; { for (int u = 0; u < N; ++u) if (dsu.find(u) == u) { ccsize2cnt[dsu.sz[u]] += 1; } } vector dp(N + 1, N + 1); { dp[0] = 0; for (auto [sz, cnt] : ccsize2cnt) { for (int r = 0; r < sz; ++r) { deque> dq; for (int i = r; i <= N; i += sz) { while (dq.size() && (i - dq.front().second) > sz * cnt) dq.pop_front(); dq.emplace_back(dp[i] - (i / sz + 1), i); if (dq.front().second != i) { dp[i] = min(dp[i], dq.front().first + (i / sz + 1)); } } } } } for (int i = 1; i <= N; ++i) { cout << (dp[i] > N ? -1 : dp[i] - 1) << "\n"; } }