#include<bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()
#define sz(x) ( (int)(x).size() )
using LL = long long;
mt19937 rng( (uint32_t)chrono::steady_clock::now().time_since_epoch().count() );
struct Dsu {
vector<int> pSet, nEle;
LL nEdge;
vector<map<int, set<int> > > edge;
vector<set<int> > in, out;
queue<pair<int, int> > q;
Dsu(int nSet) {
pSet.assign(nSet, 0); iota(all(pSet), 0);
nEle.assign(nSet, 1);
nEdge = 0;
edge.assign(nSet, {});
in.assign(nSet, {});
out.assign(nSet, {});
}
int findSet(int i) { return i ^ pSet[i] ? pSet[i] = findSet(pSet[i]) : i; }
void unite(int i, int j) {
i = findSet(i); j = findSet(j);
if (i == j) return ;
if (nEle[i] > nEle[j]) swap(i, j);
nEdge -= (LL)sz(edge[i][j]) * nEle[j]
+ (LL)sz(edge[j][i]) * nEle[i];
for (const auto &k : edge[i][j]) {
out[k].erase(j);
in[j].erase(k);
}
edge[i].erase(j);
for (const auto &k : edge[j][i]) {
out[k].erase(i);
in[i].erase(k);
}
edge[j].erase(i);
nEdge += (LL)nEle[i] * nEle[j] * 2;
nEdge -= (LL)sz(in[i]) * nEle[i] + (LL)sz(in[j]) * nEle[j];
for (const auto &k : in[i]) {
in[j].emplace(k);
if (edge[j].find(findSet(k) ) != edge[j].end() ) q.emplace(j, k);
out[k].erase(i); edge[findSet(k)][i].erase(k);
out[k].emplace(j); edge[findSet(k)][j].emplace(k);
}
for (const auto &k : edge[i]) {
for (const auto &t : k.second) {
edge[j][k.first].emplace(t);
if (edge[k.first].find(j) != edge[k.first].end() ) q.emplace(k.first, j);
}
}
nEdge += (LL)sz(in[j]) * (nEle[i] + nEle[j]);
pSet[i] = j;
nEle[j] += nEle[i];
}
void doQ() {
while (sz(q) ) {
unite(q.front().first, q.front().second);
q.pop();
}
}
};
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
#ifdef FourLeafClover
freopen("input", "r", stdin);
#endif // FourLeafCLover
int n, m; cin >> n >> m;
Dsu dsu(n);
while (m--) {
int u, v; cin >> u >> v; --u; --v;
int i = dsu.findSet(u), j = dsu.findSet(v);
if (i ^ j && dsu.out[u].find(j) == dsu.out[u].end() ) {
dsu.out[u].emplace(j); dsu.in[j].emplace(u);
dsu.edge[i][j].emplace(u);
dsu.nEdge += dsu.nEle[j];
if (dsu.edge[j].find(i) != dsu.edge[j].end() ) {
dsu.q.emplace(i, j);
dsu.doQ();
}
}
// for (int i = 0; i < n; ++i) {
// cerr << i + 1 << " in " << dsu.findSet(i) + 1 << '\n';
// if (i == dsu.findSet(i) ) {
// for (const auto &j : dsu.in[i]) cerr << j + 1 << ' ';
// cerr << '\n';
// for (const auto &j : dsu.out[i]) cerr << j + 1 << ' ';
// cerr << '\n';
// }
// }
// cerr << "end\n";
cout << dsu.nEdge << '\n';
}
return 0;
}
