#include <bits/stdc++.h>
using namespace std;
void setup()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}
int par[100000], n, m, a, b;
long long sz[100000], res;
set<int> c[100000], g[100000], r[100000];
deque<pair<int, int>> edge;
inline int Get(int inp)
{
return (inp == par[inp] ? inp : par[inp] = Get(par[inp]));
}
inline void Check(int ina, int inb)
{
g[ina].insert(inb);
r[inb].insert(ina);
if (g[inb].find(ina) != g[inb].end())
{
edge.push_back({ina, inb});
}
}
inline int all(int inp)
{
return c[inp].size() + g[inp].size() + r[inp].size();
}
inline void Combine(int ina, int inb)
{
ina = Get(ina);
inb = Get(inb);
if (ina == inb)
{
return;
}
if (all(ina) < all(inb))
{
swap(ina, inb);
}
res += sz[ina] * c[inb].size() + sz[inb] * c[ina].size(); // part of A to child B and reverse
sz[ina] += sz[inb];
par[inb] = ina;
for (auto & i : c[inb])
{
if (c[ina].find(i) != c[ina].end())
// if this node is child of both A and B, they're counted twice from above
{
res -= sz[ina];
}
else
{
c[ina].insert(i);
}
}
g[ina].erase(inb);
g[inb].erase(ina);
r[ina].erase(inb);
r[inb].erase(ina);
for (auto & i : g[inb])
{
r[inb].erase(i);
Check(ina, i);
}
for (auto & i : r[inb])
{
g[inb].erase(i);
Check(i, ina);
}
}
int main()
{
setup();
cin >> n >> m;
for (int i = 0; i < n; ++i)
{
par[i] = i;
sz[i] = 1;
c[i] = {i};
}
while (m--)
{
cin >> a >> b;
a--;
b--;
b = Get(b);
if (Get(a) != b && c[b].find(a) == c[b].end())
{
c[b].insert(a);
res += sz[b];
a = Get(a);
Check(a, b);
while (!edge.empty())
{
Combine(edge.front().first, edge.front().second);
edge.pop_front();
}
}
cout << res << "\n";
}
return 0;
}
