#include <iostream>
#include <numeric>
#include <queue>
#include <set>
#include <vector>
class joitter_dsu {
private:
int n;
std::vector<int> par;
std::vector<int64_t> size;
std::vector<std::set<int>> in, comps_in; // in[u] = set of original nodes going into comp u
// comps_in[u] = the same set as before, but instead of the original nodes we store components
std::vector<std::set<std::pair<int, int>>> out; // out[u] = set of {u_orig, v} edges coming out of comp u
std::queue<std::pair<int, int>> join_queue;
int root(int u) { return u == par[u] ? u : par[u] = root(par[u]); }
void merge(int u, int v) {
u = root(u), v = root(v);
if (u == v) {
return;
}
par[v] = u;
size[u] += size[v];
}
void erase_edge(int u_orig, int v_orig) {
int u = root(u_orig), v = root(v_orig);
in[v].erase(u_orig);
out[u].erase({u_orig, v});
}
bool insert_edge(int u_orig, int v_orig) {
int u = root(u_orig), v = root(v_orig);
if (u == v or in[v].contains(u_orig)) {
return false;
}
out[u].insert({u_orig, v});
in[v].insert(u_orig);
comps_in[v].insert(u);
if (comps_in[u].contains(v)) {
join_queue.push({u, v});
}
return true;
}
void join(int u, int v) {
if (u == v) {
return;
}
if (in[v].size() + out[v].size() > in[u].size() + out[u].size()) {
std::swap(u, v);
}
ans -= in[u].size() * size[u] + size[u] * (size[u] - 1);
ans -= in[v].size() * size[v] + size[v] * (size[v] - 1);
std::vector<std::pair<int, int>> insert, erase;
for (auto &[x, y] : out[v]) {
erase.push_back({x, y});
if (y != u) { // exclude internal edges
insert.push_back({x, y});
}
}
for (const int &i : in[v]) {
erase.push_back({i, v});
if (root(i) != u) { // same as above
insert.push_back({i, v});
}
}
for (auto &[x, y] : erase) {
erase_edge(x, y);
}
merge(u, v);
for (auto &[x, y] : insert) {
insert_edge(x, y);
}
ans += in[u].size() * size[u] + size[u] * (size[u] - 1);
}
public:
int64_t ans;
joitter_dsu(int n) : n(n), par(n), size(n, 1), in(n), comps_in(n), out(n), ans(0) {
std::iota(par.begin(), par.end(), 0);
}
void add(int u, int v) {
if (!insert_edge(u, v)) {
return;
}
ans += size[root(v)];
while (!join_queue.empty()) {
auto [x, y] = join_queue.front();
join_queue.pop();
join(x, y);
}
}
};
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n, m;
std::cin >> n >> m;
joitter_dsu dsu(n);
for (int i = 0, u, v; i < m; ++i) {
std::cin >> u >> v;
dsu.add(u - 1, v - 1);
std::cout << dsu.ans << '\n';
}
}
