#include using namespace std; struct iofast_t { iofast_t() { ios::sync_with_stdio(false); cin.tie(nullptr); } } iofast; struct uns_t {} uns; template auto vec(Element init, Head arg, Args ...args) { if constexpr (sizeof...(Args) == 0) return std::vector(arg, init); else return std::vector(arg, vec(init, args...)); } template auto vec(uns_t, Head arg, Args ...args) { return vec(Element(), arg, args...); } template > T &chmin(T &l, T r, Compare &&f = less()) { return l = min(l, r, f); } template > T &chmax(T &l, T r, Compare &&f = less()) { return l = max(l, r, f); } #include #include using mint = atcoder::modint1000000007; template struct ddsu; template struct ddsu { ddsu(int n = 0, T v = T()): dsu_(n), data_(n, v) { } explicit ddsu(std::vector v): dsu_(std::size(v)), data_() { data_ = std::move(v); } auto merge(int a, int b) { a = dsu_.leader(a); b = dsu_.leader(b); if (a == b) { return a; } int c = dsu_.merge(a, b); data_[c] = Merge( std::move(data_[a]), std::move(data_[b]) ); return c; } auto same(int a, int b) const { return dsu_.same(a, b); } auto leader(int a) const { return dsu_.leader(a); } auto size(int a) const { return dsu_.size(a); } auto groups() const { return dsu_.groups(); } auto &data(int a) noexcept { return data_[dsu_.leader(a)]; } const auto &data(int a) const noexcept { return data_[dsu_.leader(a)]; } private: mutable atcoder::dsu dsu_; std::vector data_; }; auto dmerge(vector> x, vector> y) { if (size(x) < size(y)) { swap(x, y); } if (size(x) != size(y)) { for (auto &[s, p] : y) { x.push_back({ s, 0 }); } return x; } copy(begin(y), end(y), back_inserter(x)); for (auto &[s, p] : x) { p /= 2; } return x; } int main() { int n, m; cin >> n >> m; ddsu dsu([&] { auto v = vec>(uns, n, 1); for (int i = 0; i < n; ++i) { v[i] = vec(make_tuple(i, mint(1)), 1); } return v; }()); while (m--) { int a, b; cin >> a >> b; --a; --b; dsu.merge(a, b); } auto ans = vec(uns, n); for (auto _ : dsu.groups()) { for (auto [s, p] : dsu.data(_[0])) { ans[s] = p; } } for (auto v : ans) { cout << v.val() << endl; } }