#include <bits/stdc++.h>
using i64 = long long;
#ifdef DEBUG
#include "debug.h"
#else
#define debug(...) void(23)
#endif
int N;
i64 ans = 0;
std::vector<int> f;
std::vector<int> siz;
std::vector<int> wei;
std::vector<std::set<int>> gr;
std::vector<std::set<int>> adj;
std::vector<std::set<int>> rdj;
std::vector<std::set<int>> con;
std::vector<std::set<int>> ron;
int get(int x) {
if (x == f[x]) {
return x;
}
return f[x] = get(f[x]);
}
void add_edge(int a, int b);
std::mt19937 rng(23);
void unite(int a, int b) {
if (wei[a] > wei[b]) {
std::swap(a, b);
}
debug("unite", a, b);
for (auto i : gr[a]) {
if (con[i].count(b)) {
wei[a] -= 1;
wei[b] -= 1;
ans -= siz[b];
ron[b].erase(i);
con[i].erase(b);
}
}
std::vector<int> err;
for (auto i : ron[a]) {
if (get(i) == b) {
wei[a] -= 1;
wei[b] -= 1;
ans -= siz[a];
con[i].erase(a);
err.emplace_back(i);
// ron[a].erase(i);
}
}
debug(ans);
for (auto i : err) {
ron[a].erase(i);
}
std::vector<std::pair<int, int>> nedges;
for (auto i : gr[a]) {
for (auto j : con[i]) {
wei[a] -= 1;
wei[j] -= 1;
ans -= siz[j];
debug(a, j);
ron[j].erase(i);
nedges.emplace_back(i, j);
}
con[i].clear();
}
for (auto j : ron[a]) {
wei[a] -= 1;
wei[get(j)] -= 1;
debug(j, a);
ans -= siz[a];
con[j].erase(a);
nedges.emplace_back(j, a);
}
ron[a].clear();
debug(ans);
ans += 2LL * siz[b] * siz[a];
ans += 1LL * siz[a] * ron[b].size();
debug(ans);
f[a] = b;
siz[b] += siz[a];
wei[b] += wei[a];
for (auto i : gr[a]) {
gr[b].emplace(i);
}
adj[a].clear();
rdj[a].clear();
gr[a].clear();
for (auto[i, j] : nedges) {
add_edge(i, j);
}
return;
}
void add_edge(int a, int b) {
debug(a, b);
int ca = get(a);
int cb = get(b);
if (ca == cb) {
return;
} else if (adj[cb].count(ca)) {
debug(ca, cb);
adj[cb].erase(ca);
rdj[ca].erase(cb);
unite(ca, cb);
} else {
if (!con[a].count(cb)) {
wei[ca] += 1;
wei[cb] += 1;
ans += siz[cb];
con[a].emplace(cb);
ron[cb].emplace(a);
adj[ca].emplace(cb);
rdj[cb].emplace(ca);
}
}
debug(ans);
}
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
int M;
std::cin >> N >> M;
f.resize(N);
std::iota(f.begin(), f.end(), 0);
siz.assign(N, 1);
wei.assign(N, 1);
adj.assign(N, {});
rdj.assign(N, {});
con.assign(N, {});
ron.assign(N, {});
gr.assign(N, {});
for (int i = 0; i < N; ++i) {
gr[i].emplace(i);
}
while (M--) {
int A, B;
std::cin >> A >> B;
--A, --B;
add_edge(A, B);
std::cout << ans << '\n';
debug();
}
return 0;
}
