#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define tiii tuple<int, int, int>
#define endl '\n'
#define int ll
using namespace std;
class DSU
{
private:
vector<int> par;
public:
// 0 = in, 1 = out
vector<set<tiii>> deg;
vector<int> cnt, indeg;
int edges = 0;
DSU(int n)
{
par.resize(n, 0);
cnt.resize(n, 1);
deg.resize(n);
indeg.resize(n, 0);
iota(par.begin(), par.end(), 0);
}
int find(int x)
{
if (par[x] == x)
return x;
return par[x] = find(par[x]);
}
bool uni(int a, int b)
{
a = find(a);
b = find(b);
if (a == b)
return false;
if (deg[a].size() < deg[b].size())
swap(a, b);
par[b] = a;
vector<pii> unis;
int delta = 0;
int delta_a = 0;
int delta_b = 0;
vector<pair<int, tiii>> rem, ins;
for (auto [v, t, p] : deg[b])
{
if (find(v) == a)
{
if (t == 0 && p != -1)
{
edges -= cnt[b];
delta_a++;
}
else if (p != -1)
{
edges -= cnt[a];
delta_b++;
}
rem.push_back({a, {v, t ^ 1, p}});
rem.push_back({b, {v, t, p}});
continue;
}
if (t == 0 && p != -1)
{
if (!deg[a].count({v, 0, p}))
edges += cnt[a];
else
delta++;
}
ins.push_back({a, {v, t, p}});
rem.push_back({v, {b, t ^ 1, p}});
ins.push_back({v, {a, t ^ 1, p}});
}
edges += (indeg[a] - delta - delta_b) * cnt[b];
indeg[a] += indeg[b] - delta - delta_a - delta_b;
indeg[b] = 0;
edges += 2 * cnt[a] * cnt[b];
cnt[a] += cnt[b];
for (auto x : rem)
deg[x.first].erase(x.second);
for (auto x : ins)
{
deg[x.first].insert(x.second);
int v = get<0>(x.second);
if (get<2>(x.second) == -1 && deg[a].count({v, 1, -1}) && deg[v].count({a, 1, -1}))
unis.push_back({a, v});
}
for (pii &p : unis)
uni(p.first, p.second);
return true;
}
void insert_edge(int a, int b)
{
if (find(a) == find(b))
return;
b = find(b);
if (deg[find(a)].count({b, 1, a}))
return;
edges += cnt[b];
deg[find(a)].insert({b, 1, a});
deg[find(a)].insert({b, 1, -1});
deg[b].insert({find(a), 0, a});
deg[b].insert({find(a), 0, -1});
a = find(a);
indeg[b]++;
if (deg[a].count({b, 1, -1}) && deg[b].count({a, 1, -1}))
uni(a, b);
}
};
signed main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int N, M;
cin >> N >> M;
DSU dsu(N);
for (int i = 0; i < M; i++)
{
int a, b;
cin >> a >> b;
--a;
--b;
dsu.insert_edge(a, b);
cout << dsu.edges << endl;
}
}
