#include <iostream>
#include <map>
#include <numeric>
#include <set>
#include <vector>
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n, m;
std::cin >> n >> m;
std::vector<int> par(n);
std::iota(par.begin(), par.end(), 0);
std::vector<std::map<int, int>> edges(n); // edges[u][v] = the number of edges from u to v
std::vector<int64_t> in(n), size(n, 1); // in[u] = the number of edges in total into u
// size[u] = the size of component u
std::vector<std::set<int>> into(n), outof(n); // into[u] = the set of nodes coming into u
// outof[u] = the set of nodes coming out of u
int64_t ans = 0;
auto root = [&](auto &&self, int u) -> int {
return u == par[u] ? u : par[u] = self(self, par[u]);
};
// we assume we're already dealing with roots that are not equal
auto merge = [&](auto &&self, int u, int v) {
if (u == v) {
return;
}
// make sure the latter small to large (part 2) is efficient
if (into[v].size() > into[u].size()) {
std::swap(u, v);
}
par[v] = u;
ans -= edges[u][v] * size[v] + edges[v][u] * size[u]; // remove in between edges
in[v] -= edges[u][v], in[u] -= edges[v][u]; // correct in[u/v] to exclude in between edges
ans -= in[u] * size[u] + in[v] * size[v]; // remove outer edges
ans -= size[u] * (size[u] - 1) + size[v] * (size[v] - 1); // remove internal edges
std::set<int> additional; // additional nodes that lie on the intersection that we'll also have to merge
// add nodes on the path
// step #1: u->node->v
if (outof[u].size() < into[v].size()) {
for (int i : outof[u]) {
if (into[v].contains(i)) {
additional.insert(root(root, i));
}
}
} else {
for (int i : into[v]) {
if (outof[u].contains(i)) {
additional.insert(root(root, i));
}
}
}
// step #2: v->node->u
if (outof[v].size() < into[u].size()) {
for (int i : outof[v]) {
if (into[u].contains(i)) {
additional.insert(root(root, i));
}
}
} else {
for (int i : into[u]) {
if (outof[v].contains(i)) {
additional.insert(root(root, i));
}
}
}
// small to large merging of edges[][] and into[]
// part 1: edges[v][_] = edges[u][_]
if (edges[v].size() < edges[u].size()) {
for (auto &[a, b] : edges[v]) {
edges[u][a] += b;
}
} else {
for (auto &[a, b] : edges[u]) {
edges[v][a] += b;
}
std::swap(edges[u], edges[v]);
}
// part 2: edges[_][v] = edges[_][u]
for (int i : into[v]) {
edges[i][u] += edges[i][v];
into[u].insert(i);
}
// part 3: outof[v] is now outof[u]
if (outof[v].size() < outof[u].size()) {
for (int i : outof[v]) {
outof[u].insert(i);
}
} else {
for (int i : outof[u]) {
outof[v].insert(i);
}
std::swap(outof[u], outof[v]);
}
in[u] += in[v];
size[u] += size[v];
ans += in[u] * size[u] + size[u] * (size[u] - 1); // re add to answer for the updated node
for (int i : additional) {
self(self, u, i);
}
};
while (m--) {
int u, v;
std::cin >> u >> v;
int u_orig = u - 1, v_orig = v - 1;
u = root(root, u - 1), v = root(root, v - 1);
if (u == v or into[v].contains(u_orig)) {
std::cout << ans << '\n';
continue;
}
edges[u][v]++, in[v]++, into[v].insert(u_orig), outof[u].insert(v_orig);
ans += size[v];
if (edges[v][u]) {
merge(merge, u, v);
}
std::cout << ans << '\n';
}
}
