#include <iostream>
#include <queue>
#include <set>
using namespace std;
const int N = 1<<17;
int Par[N], Sz[N];
long long Ans;
set<int> dir[N], rev[N], imd[N];
queue<pair<int, int>> Q;
int root(int v){
return (Par[v] == v ? v : Par[v] = root(Par[v]));
}
void AddEdge(int A, int B){
dir[A].insert(B);
rev[B].insert(A);
if (dir[B].find(A) != dir[B].end())
Q.push({A, B});
}
void connect(int A, int B){
if (A == B)
return;
if (imd[A].size() + dir[A].size() + rev[A].size() < imd[B].size() + dir[B].size() + rev[B].size())
swap(A, B);
Ans += 1LL * Sz[B] * imd[A].size() + 1LL * Sz[A] * imd[B].size();
Par[B] = A;
Sz[A] += Sz[B];
for (int i : imd[B]){
if (imd[A].find(i) == imd[A].end())
imd[A].insert(i);
else
Ans -= Sz[A];
}
dir[A].erase(B), dir[B].erase(A);
rev[A].erase(B), rev[B].erase(A);
for (int i : dir[B]){
rev[i].erase(B);
AddEdge(A, i);
}
for (int i : rev[B]){
dir[i].erase(B);
AddEdge(i, A);
}
}
int main(){
ios_base::sync_with_stdio(false); cin.tie(NULL);
for (int i = 1;i<N;i++)
Par[i] = i, Sz[i] = 1, imd[i].insert(i);
int n, m, a, b, A, B;
cin>>n>>m;
while (m--){
cin>>a>>b;
A = root(a), B = root(b);
if (A != B and imd[B].find(a) == imd[B].end()){
imd[B].insert(a);
Ans += Sz[B];
AddEdge(A, B);
while (Q.size() > 0){
auto [c, d] = Q.front(); Q.pop();
connect(root(c), root(d));
}
}
cout<<Ans<<'\n';
}
}
