#include<bits/stdc++.h>
using namespace std;
#define f first
#define s second
using ll = long long;
const int mxN = 100000;
int par[mxN + 5];
ll sz[mxN + 5];
ll result = 0;
set<int> ccs[mxN + 5], ou[mxN + 5], in[mxN + 5];
queue< pair<int, int> > to_merge;
void weak_connection(int x, int y) {
ou[x].insert(y); in[y].insert(x);
if (ou[y].count(x)) to_merge.emplace(x, y);
}
int tot_sz(int x) {
return ccs[x].size() + in[x].size() + ou[x].size();
}
int find(int x) {
return (x == par[x] ? x: par[x] = find(par[x]));
}
void unite_set(int x, int y) {
if (x == y) return ;
if (tot_sz(x) < tot_sz(y)) swap(x, y);
result += sz[y] * ccs[x].size() + sz[x] * ccs[y].size();
par[y] = x; sz[x] += sz[y];
for (int u: ccs[y]) {
if (ccs[x].count(u)) result -= sz[x];
else ccs[x].emplace(u);
}
ou[x].erase(y); in[x].erase(y);
ou[y].erase(x); in[y].erase(x);
for (int u: ou[y]) {
in[u].erase(y);
weak_connection(x, u);
}
for (int u: in[y]) {
ou[u].erase(y);
weak_connection(u, x);
}
}
int main() {
cin.tie(0)->sync_with_stdio(0);
int n, m; cin >> n >> m;
for (int i = 1; i <= n; i++) {
par[i] = i;
sz[i] = 1;
ccs[i].insert(i);
}
int x, y;
while (m--) {
cin >> x >> y;
y = find(y);
if (find(x) != y && !ccs[y].count(x)) {
ccs[y].emplace(x);
result += sz[y];
x = find(x);
weak_connection(x, y);
while (!to_merge.empty()) {
tie(x, y) = to_merge.front();
to_merge.pop();
unite_set(find(x), find(y));
}
}
cout << result << "\n";
}
return 0;
}
/*
4 6
1 2
2 3
3 2
1 3
3 4
4 3
*/
