#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define TruongPham int main()
#define sz 1000006
const int mod = 1e9 +7;
const int base = 31;
int n, q;
set<int> listIn[sz], listOut[sz]; // danh sach cac dinh vao va ra cua mot thanh phan lien thong
set<int> child[sz]; // child[i] la nhung thang co noi den i
int root[sz];
int numb[sz];
ll ans =0;
vector<pair<int,int>> store; // dung de luu tru cac canh vo huong
int findroot(int u)
{
if (u==root[u]) return u;
int rootu = findroot(root[u]);
root[u] = rootu;
return rootu;
}
void add(int u, int v)
{
listOut[u].insert(v);
listIn[v].insert(u);
if (listOut[v].find(u) != listOut[v].end()) // u -> v va v -> u
{
store.push_back({u,v});
}
}
int total(int u)
{
return (int)child[u].size() + (int)listIn[u].size() + (int)listOut[u].size();
// tong so dinh trong tplt u + so dinh di vao u + so dinh tu u di ra
}
void unite(int rootu, int rootv)
{
if (rootu == rootv)
{
return;
}
if (total(rootu) < total(rootv))
{
swap(rootu, rootv);
}
auto rootu_out = listOut[rootu].find(rootv);
auto rootu_in = listIn[rootu].find(rootv);
auto rootv_out = listOut[rootv].find(rootu);
auto rootv_in = listIn[rootv].find(rootu);
if (rootu_out != listOut[rootu].end())
{
listOut[rootu].erase(rootu_out);
}
if (rootu_in != listIn[rootu].end())
{
listIn[rootu].erase(rootu_in);
}
if (rootv_out != listOut[rootv].end())
{
listOut[rootv].erase(rootv_out);
}
if (rootv_in != listIn[rootv].end())
{
listIn[rootv].erase(rootv_in);
}
ans += (1ll* child[rootu].size() * numb[rootv] + 1ll* child[rootv].size() * numb[rootu]);
numb[rootu] += numb[rootv];
//ans += (1ll * numb[rootv] *(int)listIn[rootu].size() + 1ll* numb[rootu] *(int)listIn[rootv].size());
// tien hanh noi tat ca cua v vao u
// xoa tat ca thong tin lien quan den v
root[rootv] = rootu;
for (auto it: child[rootv])
{
if (child[rootu].find(it) != child[rootu].end())
{
ans -= numb[rootu]; // nhung thang co ton tai o ca rootu vaf rootv da bi cong nham
// mot luong la tong tplt moi
// do truoc do chung ta co ans += numb[rootv] da bao gom nhung thang trung roi
} else
{
child[rootu].insert(it); // de kiem tra neu khi noi 1 canh ma ta da noi roi;
}
}
child[rootv].clear();
for (auto it:listIn[rootv]) // x -> rootv
{
if (listOut[it].find(rootv) != listOut[it].end())
{
listOut[it].erase(listOut[it].find(rootv));
}
add(it, rootu);
}
for (auto it:listOut[rootv]) // rootv -> x
{
if (listIn[it].find(rootv) != listIn[it].end())
{
listIn[it].erase(listIn[it].find(rootv));
}
add(rootu, it);
}
listIn[rootv].clear();
listOut[rootv].clear();
}
TruongPham
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin>>n>>q;
for (int i=1;i<=n;i++)
{
root[i] = i;
numb[i] =1;
child[i].insert(i);
} // khoi tao tplt dinh i
for (int i=1;i<=q;i++)
{
int u, v;
cin>>u>>v;
int rootu = findroot(u);
int rootv = findroot(v);
if (rootu==rootv || child[rootv].find(u) != child[rootv].end()) // 2 dinh da thuoc cung mot thanh phan lien thong
{
cout<<ans<<endl;
continue;
}
child[rootv].insert(u);
ans += numb[rootv];
// khi ta noi 1 canh co huong tu u den tplt v thi ta se them duoc so luong dinh
// trong tplt v
add(rootu, rootv);
while(!store.empty())
{
pair<int,int> edge = store.back();
store.pop_back();
unite(findroot(edge.first), findroot(edge.second));
}
cout<<ans<<endl;
}
return 0;
}
