// ロンリーガールはいつまでも // 届かない夢見て #include <bits/stdc++.h> using namespace std; #ifdef LOCAL #include "algo/debug.h" #else #define debug(...) 42 #endif class dsu { public: vector<int> p, sz; vector<set<int>> child, g, rev_g; queue<pair<int, int>> que; int n; long long ans = 0; dsu(int _n) : n(_n) { p.resize(n); iota(p.begin(), p.end(), 0); sz.resize(n); fill(sz.begin(), sz.end(), 1); child.resize(n); g.resize(n); rev_g.resize(n); for (int i = 0; i < n; i++) { child[i].insert(i); } } int get(int x) { return ((p[x] == x) ? x : (p[x] = get(p[x]))); } void add(int u, int v) { g[u].insert(v); rev_g[v].insert(u); if (g[v].find(u) != g[v].end()) { que.emplace(u, v); } } int siz(int x) { return g[x].size() + rev_g[x].size() + child[x].size(); } void help(int u, int v) { if (u == v) { return; } if (siz(u) < siz(v)) { swap(u, v); } ans += static_cast<long long>(sz[u]) * static_cast<long long>(child[v].size()) + static_cast<long long>(sz[v]) * static_cast<long long>(child[u].size()); p[v] = u; sz[u] += sz[v]; for (int x : child[v]) { if (child[u].find(x) != child[u].end()) { ans -= sz[u]; } else { child[u].insert(x); } } g[v].erase(u), rev_g[u].erase(v); g[u].erase(v), rev_g[v].erase(u); for (int x : g[v]) { rev_g[x].erase(v); add(u, x); } for (int x : rev_g[v]) { g[x].erase(v); add(x, u); } } void unite(int u, int v) { v = get(v); if (get(u) != v && child[v].find(u) == child[v].end()) { child[v].insert(u); ans += sz[v]; u = get(u); add(u, v); while (!que.empty()) { auto [uu, vv] = que.front(); que.pop(); help(get(uu), get(vv)); } } } }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin >> n >> m; dsu ds(n); for (int i = 0; i < m; i++) { int u, v; cin >> u >> v; --u; --v; ds.unite(u, v); cout << ds.ans << '\n'; } return 0; }