#include<bits/stdc++.h>
using namespace std;
#define N 100005
#define fi first
#define se second
#define int long long
typedef pair<int, int> ii;
int n, m, res, siz[N], par[N];
set<int> child[N], adj[N], r_adj[N];
queue<ii> q;
int find(int u){
if (u == par[u]) return u;
return par[u] = find(par[u]);
}
void addeg(int u, int v){
adj[u].insert(v);
r_adj[v].insert(u);
if (adj[v].count(u)) q.push({u, v});
}
int sum(int u){
return child[u].size() + adj[u].size() + r_adj[u].size();
}
void unin(int u, int v){
u = find(u);
v = find(v);
if (u == v) return;
res += child[u].size() * siz[v] + child[v].size() * siz[u];
if (sum(u) < sum(v)) swap(u, v);
siz[u] += siz[v];
par[v] = u;
for (auto x : child[v]){
if (child[u].find(x) != child[u].end()) res -= siz[u];
else child[u].insert(x);
}
adj[u].erase(v);
r_adj[u].erase(v);
adj[v].erase(u);
r_adj[v].erase(u);
for (auto x : adj[v]){
r_adj[x].erase(v);
addeg(u, x);
}
for (auto x : r_adj[v]){
adj[x].erase(v);
addeg(x, u);
}
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(NULL);
cin >> n >> m;
for (int i = 1; i <= n; i++){
siz[i] = 1;
par[i] = i;
child[i].insert(i);
}
for (int i = 1; i <= m; i++){
int u, v;
cin >> u >> v;
v = find(v);
if (find(u) != v && child[v].find(u) == child[v].end()){
child[v].insert(u);
res += siz[v];
u = find(u);
addeg(u, v);
while (!q.empty()){
int u = q.front().fi;
int v = q.front().se;
unin(u, v);
q.pop();
}
}
cout << res << "\n";
}
return 0;
}
