#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define all(aaa) aaa.begin(), aaa.end()
const int N = 1e5 + 5;
int w[N];
set<int> *members[N], *ingoing_ver[N], *outgoing_gr[N], *ingoing_gr[N];
ll ans = 0;
int n, m;
int find_set(int x) {
return w[x] < 0 ? x : w[x] = find_set(w[x]);
}
void mrg(int x, int y) {
x = find_set(x);
y = find_set(y);
if (x == y)
return;
ans -= members[x]->size() * (ll)(members[x]->size() - 1);
ans -= members[y]->size() * (ll)(members[y]->size() - 1);
ans -= ingoing_ver[x]->size() * (ll)members[x]->size();
ans -= ingoing_ver[y]->size() * (ll)members[y]->size();
if (members[x]->size() + ingoing_ver[x]->size() <
members[y]->size() + ingoing_ver[y]->size()) {
swap(members[x], members[y]);
swap(ingoing_ver[x], ingoing_ver[y]);
}
for (const int &el : *members[y]) {
members[x]->insert(el);
ingoing_ver[x]->erase(el);
}
for (const int &el : *ingoing_ver[y]) {
if (!members[x]->count(el)) {
ingoing_ver[x]->insert(el);
}
}
ans += ingoing_ver[x]->size() * (ll)members[x]->size();
ans += members[x]->size() * (ll)(members[x]->size() - 1);
if (ingoing_gr[x]->size() + outgoing_gr[x]->size() <
ingoing_gr[y]->size() + outgoing_gr[y]->size()) {
swap(x, y);
swap(members[x], members[y]);
swap(ingoing_ver[x], ingoing_ver[y]);
}
ingoing_gr[y]->erase(x);
ingoing_gr[x]->erase(y);
for (const int &el : *ingoing_gr[y]) {
ingoing_gr[x]->insert(el);
outgoing_gr[el]->erase(y);
outgoing_gr[el]->insert(x);
}
vector<int> to_mrg;
outgoing_gr[y]->erase(x);
outgoing_gr[x]->erase(y);
for (const int &el : *outgoing_gr[y]) {
outgoing_gr[x]->insert(el);
ingoing_gr[el]->erase(y);
ingoing_gr[el]->insert(x);
if (ingoing_gr[el]->count(x) &&
outgoing_gr[el]->count(x)) {
to_mrg.push_back(el);
}
}
w[y] = x;
for (const int &el : to_mrg) {
mrg(el, x);
}
}
void add_edge(int x, int y) {
y = find_set(y);
if (find_set(x) == y)
return;
if (!ingoing_ver[y]->count(x)) {
ans += members[y]->size();
ingoing_ver[y]->insert(x);
}
x = find_set(x);
ingoing_gr[y]->insert(x);
outgoing_gr[x]->insert(y);
if (outgoing_gr[y]->count(x)) {
mrg(x, y);
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, m;
cin >> n >> m;
for (int i = 0; i < n; i++) {
w[i] = -1;
ingoing_gr[i] = new set<int>();
outgoing_gr[i] = new set<int>();
ingoing_ver[i] = new set<int>();
members[i] = new set<int>();
members[i]->insert(i);
}
for (int i = 0; i < m; i++) {
int x, y;
cin >> x >> y;
x--, y--;
add_edge(x, y);
cout << ans << "\n";
}
return 0;
}
