#include <bits/stdc++.h>
using namespace std;
long long int res=0;
vector<int>dsu,sz;
vector<set<int>>v,g,g1;
queue<pair<int,int>>q;
int vfind(int a)
{
if(dsu[a]==a)return a;
return dsu[a]=vfind(dsu[a]);
}
void dodadi(int a,int b)
{
if(a==b)return;
g[a].insert(b);
g1[b].insert(a);
if(g[b].count(a))q.push({a,b});
}
int golemina(int a)
{
return g[a].size()+v[a].size()+g1[a].size();
}
void unija(int a,int b)
{
if(a==b)return;
if(golemina(b)>golemina(a))swap(a,b);
res+=sz[a]*v[b].size()+sz[b]*v[a].size();
dsu[b]=a;
sz[a]+=sz[b];
for(int i:v[b])
{
if(v[a].count(i))res-=sz[a];
else v[a].insert(i);
}
g[a].erase(b);
g1[a].erase(b);
g[b].erase(a);
g1[b].erase(a);
for(int i:g[b])
{
g1[i].erase(b);
dodadi(a,i);
}
for(int i:g1[b])
{
g[i].erase(b);
dodadi(i,a);
}
}
int main()
{
int n,m,a,b;
cin>>n>>m;
v.resize(n+1);
g.resize(n+1);
g1.resize(n+1);
dsu.resize(n+1);
sz.resize(n+1);
for(int i=1;i<=n;i++)
{
dsu[i]=i;
sz[i]=1;
v[i].insert(i);
}
for(int i=0;i<m;i++)
{
cin>>a>>b;
b=vfind(b);
if(vfind(a)!=b&&!v[b].count(a))
{
v[b].insert(a);
a=vfind(a);
res+=sz[b];
dodadi(a,b);
while(!q.empty())
{
auto p=q.front();
q.pop();
unija(vfind(p.first),vfind(p.second));
}
}
cout<<res<<"\n";
}
}
