#include <bits/stdc++.h>
using namespace std;
const int N=1e5+2;
int n,m;
set<int> graph[N],rgraph[N],child[N];
int comp[N];
int size_comp[N];
int find(int point)
{
//cout<<point<<" "<<comp[point]<<'\n';
if(comp[point]==point)
{
return point;
}
else
{
int t=find(comp[point]);
comp[point]=t;
return t;
}
}
long long ans=0;
vector<pair<int,int>> to_merge;
void merge_weak(int a,int b)
{
graph[a].insert(b);
rgraph[b].insert(a);
if(graph[b].count(a))
to_merge.push_back({a,b});
}
int dsu_size(int a)
{
return graph[a].size()+rgraph[a].size()+child[a].size();
}
void uneste(int a,int b)
{
if(find(a)==find(b))
return;
if(dsu_size(a)<dsu_size(b))
swap(a,b);
ans+=size_comp[a]*child[b].size()+size_comp[b]*child[a].size();
size_comp[a]+=size_comp[b];
comp[b]=a;
for(auto u:child[b])
{
if(child[a].count(u))
ans-=size_comp[a];
else
child[a].insert(u);
}
graph[a].erase(b);
rgraph[a].erase(b);
graph[b].erase(a);
rgraph[b].erase(a);
for(auto u:graph[b])
{
rgraph[u].erase(b);
merge_weak(a,u);
}
for(auto u:rgraph[b])
{
graph[u].erase(b);
merge_weak(u,a);
}
}
void citeste()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
size_comp[i]=1;
comp[i]=i;
child[i].insert(i);
}
for(int i=1;i<=m;i++)
{
int a,b;
cin>>a>>b;
int top=find(b);
if(find(a)!=find(b)&&child[top].find(a)==child[top].end())
{
child[top].insert(a);
ans+=size_comp[top];
int top2=find(a);
merge_weak(top2,top);
while(to_merge.empty()==false)
{
int x,y;
tie(x,y)=to_merge.back();
to_merge.pop_back();
uneste(find(x),find(y));
}
}
cout<<ans<<'\n';
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
citeste();
return 0;
}
