#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 1e5;
long long totalEdges = 0;
int parent[MAX_N + 1], sizee[MAX_N + 1];
set<int> inVertices[MAX_N + 1], inComponents[MAX_N + 1], outComponents[MAX_N + 1];
set<int> vert[MAX_N + 1];
int findParent(int u) {
if (parent[u] != u)
parent[u] = findParent(parent[u]);
return parent[u];
}
bool isEdgeFromVertexToComponent(int v, int c) {
return (inVertices[c].find(v) != inVertices[c].end());
}
bool isEdgeFromComponentToComponent(int u, int v) {
return (inComponents[v].find(u) != inComponents[v].end());
}
vector<pair<int, int>> coada;
void unionn(int u, int v) {
u = findParent(u);
v = findParent(v);
if (u == v)
return;
if (vert[u].size() < vert[v].size())
swap(u, v);
totalEdges -= (long long)sizee[u] * (inVertices[u].size() + sizee[u] - 1);
totalEdges -= (long long)sizee[v] * (inVertices[v].size() + sizee[v] - 1);
parent[v] = u;
sizee[u] += sizee[v];
for (int x: vert[v]) {
vert[u].insert(x);
inVertices[u].erase(x);
}
vert[v].clear();
for (int x: inVertices[v]) {
if (vert[u].find(x) == vert[u].end())
inVertices[u].insert(x);
}
inVertices[v].clear();
for (int x: inComponents[v]) {
if (outComponents[u].find(x) != outComponents[u].end())
coada.push_back({x, u});
}
for (int x: outComponents[v]) {
if (inComponents[u].find(x) != inComponents[u].end())
coada.push_back({x, u});
}
for (int x: inComponents[v]) {
inComponents[u].insert(x);
outComponents[x].insert(u);
}
for (int x: outComponents[v]) {
outComponents[u].insert(x);
inComponents[x].insert(u);
}
totalEdges += (long long)sizee[u] * (inVertices[u].size() + sizee[u] - 1);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
for (int v = 1; v <= n; v++) {
parent[v] = v, sizee[v] = 1;
vert[v].insert(v);
}
totalEdges = 0;
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
int pu = findParent(u);
int pv = findParent(v);
if (pu != pv) {
if (isEdgeFromComponentToComponent(pv, pu)) {
coada.push_back({u, v});
while (!coada.empty()) {
int u = coada.back().first, v = coada.back().second;
coada.pop_back();
unionn(u, v);
}
} else {
inComponents[pv].insert(pu);
outComponents[pu].insert(pv);
if (!isEdgeFromVertexToComponent(u, pv)) {
totalEdges += sizee[pv];
inVertices[pv].insert(u);
}
}
}
cout << totalEdges << "\n";
}
return 0;
}
