// Starcraft 2 enjoyer //
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 5;
int n, m, par[N], sz[N];
long long ans;
// point[root] = unique node IDs following this component
// in[root] = component roots that follow this component
// to[root] = component roots that this component follows
set<int> point[N], in[N], to[N];
queue<pair<int, int>> q;
int getParent(int i) {
return par[i] == i ? i : par[i] = getParent(par[i]);
}
int getSum(int i) {
// Internal edges + (size * number of unique external followers)
return sz[i] * (sz[i] - 1) + sz[i] * (int)point[i].size();
}
void combine(int u, int v) {
int pi = getParent(u);
int pj = getParent(v);
if (pi == pj) return;
// Small-to-large based on total set activity
if (sz[pi] + in[pi].size() + to[pi].size() + point[pi].size() <
sz[pj] + in[pj].size() + to[pj].size() + point[pj].size()) {
swap(pi, pj);
}
ans -= getSum(pi);
ans -= getSum(pj);
// 1. Move individual follower nodes
for (int node : point[pj]) {
if (getParent(node) != pi) point[pi].insert(node);
}
point[pj].clear();
// 2. Clean up mutual links before merging sets
in[pi].erase(pj);
to[pi].erase(pj);
in[pj].erase(pi);
to[pj].erase(pi);
// 3. Update incoming neighbors: Neighbors pointing to pj now point to pi
for (int pk : in[pj]) {
to[pk].erase(pj);
to[pk].insert(pi);
in[pi].insert(pk);
// Check if a new mutual link is formed
if (to[pi].count(pk)) q.push({pi, pk});
}
in[pj].clear();
// 4. Update outgoing neighbors: pj pointing to pk now pi points to pk
for (int pk : to[pj]) {
in[pk].erase(pj);
in[pk].insert(pi);
to[pi].insert(pk);
// Check if a new mutual link is formed
if (in[pi].count(pk)) q.push({pi, pk});
}
to[pj].clear();
// 5. Finalize DSU merge
par[pj] = pi;
sz[pi] += sz[pj];
ans += getSum(pi);
}
void add_edge(int u, int v) {
int pu = getParent(u);
int pv = getParent(v);
if (pu == pv || point[pv].count(u)) return;
// The Joitter Rule: If pv already follows pu, and we add u -> v, they merge.
if (to[pv].count(pu)) {
q.push({pu, pv});
while (!q.empty()) {
auto [curr_u, curr_v] = q.front();
q.pop();
combine(curr_u, curr_v);
}
} else {
// Normal follow: update the point set and component tracking
ans -= getSum(pv);
point[pv].insert(u);
in[pv].insert(pu);
to[pu].insert(pv);
ans += getSum(pv);
}
}
inline void solve() {
if (!(cin >> n >> m)) return;
ans = 0;
for (int x = 1; x <= n; x++) {
sz[x] = 1;
par[x] = x;
point[x].clear();
in[x].clear();
to[x].clear();
}
for (int x = 0; x < m; x++) {
int a, b;
cin >> a >> b;
add_edge(a, b);
cout << ans << "\n";
}
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
solve();
return 0;
}
