#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5 + 5, M = 3e5;
set<int> in_grp[N], out_grp[N];
set<pair<int, int>> in_ver[N];
int ans = 0, n, m;
class DSU {
int n, *par, *grp_size;
public:
DSU(int n) {
this->n = n;
par = new int[n];
grp_size = new int[n];
iota(par, par + n, 0);
fill(grp_size, grp_size + n, 1);
}
int parent(int v) {
if (v == par[v])
return v;
else
return par[v] = parent(par[v]);
}
void merge(int u, int v) {
u = parent(u), v = parent(v);
if (u == v)
return;
par[v] = u;
bool check = true;
if (in_grp[v].size() + out_grp[v].size() > in_grp[u].size() + out_grp[u].size())
swap(in_grp[v], in_grp[u]), swap(out_grp[v], out_grp[u]), check = false;
if (in_ver[v].size() > in_ver[u].size())
swap(in_ver[v], in_ver[u]);
ans -= in_ver[v].size() * grp_size[v] + in_ver[u].size() * grp_size[u] + grp_size[v] * (grp_size[v] - 1) + grp_size[u] * (grp_size[u] - 1);
in_grp[u].insert(in_grp[v].begin(), in_grp[v].end());
out_grp[u].insert(out_grp[v].begin(), out_grp[v].end());
in_ver[u].insert(in_ver[v].begin(), in_ver[v].end());
in_grp[u].erase(v);
out_grp[u].erase(v);
grp_size[u] += grp_size[v];
for (auto itr = in_ver[u].lower_bound({v, 0}); itr != in_ver[u].end() && itr->first == v;)
in_ver[u].erase(itr++);
for (auto itr = in_ver[u].lower_bound({u, 0}); itr != in_ver[u].end() && itr->first == u;)
in_ver[u].erase(itr++);
ans += in_ver[u].size() * grp_size[u] + grp_size[u] * (grp_size[u] - 1);
for (auto &i : out_grp[u]) {
in_grp[i].erase(v);
in_grp[i].insert(u);
for (auto itr = in_ver[i].lower_bound({v, 0}); itr != in_ver[i].end() && itr->first == v;)
in_ver[i].insert({u, itr->second}), in_ver[i].erase(itr++);
}
for (auto &i : in_grp[v]) {
if (in_grp[i].count(u))
merge(u, i);
}
for (auto &i : out_grp[v]) {
if (in_grp[u].count(i))
merge(u, i);
}
}
void add(int u, int v) {
int pu = parent(u), pv = parent(v);
if (pu == pv || in_ver[pv].count({pu, u}))
return;
if (in_grp[pu].count(pv)) {
merge(pu, pv);
return;
}
out_grp[pu].insert(pv);
in_grp[pv].insert(pu);
in_ver[pv].insert({pu, u});
ans += grp_size[pv];
}
};
void solveTestCase() {
cin >> n >> m;
DSU dsu(n + 1);
for (int i = 0; i < m; i++) {
int a, b;
cin >> a >> b;
dsu.add(a, b);
cout << ans << "\n";
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int test = 1;
// cin >> test;
for (int i = 1; i <= test; i++)
solveTestCase();
}
