#include <bits/stdc++.h>
using namespace std;
#define int long long
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define pb push_back
#define all(a) a.begin(), a.end()
#define endl "\n"
void printVector(vector<int> a){
for (auto x: a) cout << x << " ";
cout << endl;
}
int ans = 0;
queue<pair<int, int>> to_merge;
struct UFDS{
vector<int> link, siz;
vector<set<int>> child, graph, rgraph;
UFDS (int n){
link.resize(n+1);
for (int i = 0; i <= n; i++) link[i] = i;
siz.resize(n+1, 1);
child.resize(n+1);
graph.resize(n+1);
for (int i = 0; i <= n; ++i) child[i].insert(i);
rgraph.resize(n+1);
}
int dsu_size(int x){
return (int)(child[x].size() + graph[x].size() + rgraph[x].size());
}
int find(int x){
if (x == link[x]) return x;
return link[x] = find(link[x]);
}
void insert_conn(int x, int y){
graph[x].insert(y);
rgraph[y].insert(x);
if (graph[y].count(x)) to_merge.push({x, y});
}
void unite(int x, int y){
x = find(x);
y = find(y);
if (x == y) return;
if (dsu_size(x) < dsu_size(y)) swap(x, y);
ans += child[x].size()*siz[y] + child[y].size()*siz[x];
link[y] = x;
siz[x] += siz[y];
for (auto i: child[y]){
if (child[x].count(i) == 0) child[x].insert(i);
else ans -= siz[x];
}
graph[x].erase(y);rgraph[y].erase(x);
graph[y].erase(x);rgraph[x].erase(y);
for (auto i: graph[y]){
rgraph[i].erase(y);
insert_conn(x, i);
}
for (auto i: rgraph[y]){
graph[i].erase(y);
insert_conn(i, x);
}
}
};
void solve(){
int n, m; cin >> n >> m;
UFDS ds(n+1);
FOR(k,0,m){
int x, y; cin >> x >> y;
y = ds.find(y);
if (ds.find(x) != y && !ds.child[y].count(x)){
ds.child[y].insert(x);
ans += ds.siz[y];
x = ds.find(x);
ds.insert_conn(x, y);
while (to_merge.size()){
tie(x, y) = to_merge.front();
to_merge.pop();
ds.unite(x, y);
}
}
cout << ans << endl;
}
}
int32_t main(){
ios::sync_with_stdio(false);cin.tie(nullptr);
int t = 1; // cin >> t;
while (t--) solve();
}
