//Challenge: Accepted
#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <set>
#include <queue>
#define maxn 100005
#define ll long long
using namespace std;
set<int> adj[maxn], rev[maxn], chi[maxn];
int par[maxn];
ll siz[maxn], cnt[maxn];
ll ans = 0;
inline int find(int a) {
return a == par[a] ? a : par[a] = find(par[a]);
}
void Union(int a, int b) {
a = find(a), b = find(b);
if (a == b) return;
par[b] = a;
siz[a] += siz[b];
}
void addEdge(int a, int b);
queue<pair<int, int> > que;
void combine(int a, int b) {
//cout << a << " " << b << endl;
if (find(a) == find(b)) return;
a = find(a), b = find(b);
if (adj[a].size() + rev[a].size() + chi[a].size() < adj[b].size() + rev[b].size() + chi[b].size()) swap(a, b);
//cout << a << " " << b << endl;
//cout << siz[a] << " " << chi[b].size() << " " << siz[b] << " " << chi[a].size()<< endl;
ans += siz[a] * (chi[b].size()) + siz[b] * (chi[a].size());
adj[a].erase(b);rev[b].erase(a);
adj[b].erase(a);rev[a].erase(b);
Union(a, b);
for (int c:chi[b]) {
if (chi[a].count(c)) ans -= siz[a];
else chi[a].insert(c);
}
for (int v:adj[b]) {
rev[v].erase(b);
addEdge(a, v);
}
for (int v:rev[b]) {
adj[v].erase(b);
addEdge(v, a);
}
adj[b].clear(), rev[b].clear();
//cnt[a] = rev[a].size();
//cout << cnt[a] - ob << " " << siz[b] << " " << cnt[a] - oa << " " << siz[a] << endl;
}
void addEdge(int a, int b) {
adj[a].insert(b);
rev[b].insert(a);
if (rev[a].count(b)) {
que.push(make_pair(a, b));
}
}
int main() {
ios_base::sync_with_stdio(0);cin.tie(0);
int n, m;
cin >> n >> m;
for (int i = 1;i <= n;i++) {
par[i] = i, siz[i] = 1;
chi[i].insert(i);
}
for (int i = 0;i < m;i++) {
int a, b;
cin >> a >> b;
b = find(b);
if (find(a) == find(b) || chi[b].count(a)) {
cout << ans << "\n";
continue;
}
chi[b].insert(a);
a = find(a);
ans += siz[b];
addEdge(a, b);
while (que.size()) {
combine(que.front().first, que.front().second);
que.pop();
}
cout << ans << "\n";
}
}
/*
4 6
1 2
2 3
3 2
1 3
3 4
4 3
*/
