#include <bits/stdc++.h>
using namespace std;
#define ar array
#define sz(v) int(std::size(v))
using i64 = long long;
using pii = pair<int, int>;
const int MAXN = 1e5;
int N, M;
int sz[MAXN], parent[MAXN];
list<int> vertices[MAXN];
set<int> out[MAXN], in[MAXN];
set<int> in_v[MAXN];
i64 num_edges;
int find(int i) {
return parent[i] == i ? i : parent[i] = find(parent[i]);
}
void add_edge(int i, int j) {
int x = find(i);
int y = find(j);
if (x == y) return;
if (in_v[y].count(i)) return;
in_v[y].insert(i);
num_edges += sz[y];
queue<pii> mrg;
auto ins = [&](int x, int y) {
out[x].insert(y);
in[y].insert(x);
if (out[y].count(x)) mrg.push({x, y});
};
ins(x, y);
while (sz(mrg)) {
auto [x, y] = mrg.front(); mrg.pop();
x = find(x);
y = find(y);
if (x != y) {
if (sz[x] < sz[y]) swap(x, y);
num_edges += i64(sz(in_v[x])) * sz[y];
num_edges += i64(sz(in_v[y])) * sz[x];
out[x].erase(y);
in[x].erase(y);
for (int i : exchange(in_v[y], {})) {
if (in_v[x].count(i)) num_edges -= sz[x] + sz[y];
else in_v[x].insert(i);
}
for (int i : exchange(out[y], {})) {
if (i == x) continue;
in[i].erase(y);
ins(x, i);
}
for (int i : exchange(in[y], {})) {
if (i == x) continue;
out[i].erase(y);
ins(i, x);
}
vertices[x].splice(end(vertices[x]), vertices[y]);
parent[y] = x;
sz[x] += sz[y];
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> N >> M;
for (int i = 0; i < N; i++) {
sz[i] = 1;
parent[i] = i;
vertices[i] = {i};
in_v[i] = {i};
}
while (M--) {
int i, j;
cin >> i >> j, i--, j--;
add_edge(i, j);
cout << num_edges << '\n';
}
}
