#include <array>
#include <iostream>
#include <map>
#include <numeric>
#include <set>
#include <vector>
void small_to_large(std::set<int> &a, std::set<int> &b) {
if (b.size() < a.size()) {
for (int i : b) {
a.insert(i);
}
} else {
for (int i : a) {
b.insert(i);
}
std::swap(a, b);
}
}
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, std::set<int>>> edges(n); // edges[u][v] = size: the number of edges from u to v, contents: the original u's
std::vector<int64_t> size(n, 1); // size[u] = the size of component u
std::vector<std::set<int>> in(n), out(n); // in[u] = the set of nodes coming into u
// out[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
auto merge = [&](auto &&self, int u, int v) {
if (u == v) {
return;
}
// make sure the latter small to large (part 2) is efficient
if (in[v].size() > in[u].size()) {
std::swap(u, v);
}
par[v] = u;
ans -= edges[u][v].size() * size[v] + edges[v][u].size() * size[u]; // remove in between edges
// correct in[u/v] to exclude in between edges
for (int i : edges[u][v]) {
in[v].erase(i);
}
for (int i : edges[v][u]) {
in[u].erase(i);
}
// amortised O(m) total ^
ans -= in[u].size() * size[u] + in[v].size() * 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 common path that we have to merge
// both cases: u->node->v and v->node->u
for (auto &[u, v] : std::array<std::pair<int, int>, 2>{{{u, v}, {v, u}}}) {
if (out[u].size() < in[v].size()) {
for (int i : out[u]) {
if (in[v].contains(i)) {
additional.insert(root(root, i));
}
}
} else {
for (int i : in[v]) {
if (out[u].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]) {
small_to_large(edges[u][a], b);
}
} else {
for (auto &[a, b] : edges[u]) {
small_to_large(edges[v][a], b);
}
std::swap(edges[u], edges[v]);
}
// part 2: edges[_][v] = edges[_][u]
for (int i : in[v]) {
small_to_large(edges[i][u], edges[i][v]);
in[u].insert(i);
}
// part 3: maintain out[u]
if (out[v].size() < out[u].size()) {
for (int i : out[v]) {
out[u].insert(i);
}
} else {
for (int i : out[u]) {
out[v].insert(i);
}
std::swap(out[u], out[v]);
}
size[u] += size[v];
ans += in[u].size() * size[u] + size[u] * (size[u] - 1); // re add to answer for the updated node
// finally, merge all additional nodes
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 in[v].contains(u_orig)) {
std::cout << ans << '\n';
continue;
}
edges[u][v].insert(u_orig), in[v].insert(u_orig), out[u].insert(v_orig);
ans += size[v];
if (!edges[v][u].empty()) {
merge(merge, u, v);
}
std::cout << ans << '\n';
}
}
