#include <bits/stdc++.h>
using namespace std;
const int nmax = 1e5 + 1;
int root[nmax], sz[nmax];
long long ans;
set<int> adj[nmax], inv[nmax], child[nmax];
int find(int a) {
if(root[a] == a) {
return a;
}
return root[a] = find(root[a]);
}
queue<pair<int, int>> q;
void weak(int a, int b) {
adj[a].insert(b);
inv[b].insert(a);
if(adj[b].count(a)) {
q.push({a, b});
}
}
int ds_sz(int x) {
return child[x].size() + adj[x].size() + inv[x].size();
}
void unite(int a, int b) {
a = find(a), b = find(b);
if(a == b) {
return;
}
if(ds_sz(a) < ds_sz(b)) {
swap(a, b);
}
ans += sz[b] * child[a].size() + sz[a] * child[b].size();
root[b] = a;
sz[a] += sz[b];
for(auto it : child[b]) {
if(child[a].count(it)) {
ans -= sz[a];
} else {
child[a].insert(it);
}
}
adj[a].erase(b), adj[b].erase(a);
inv[a].erase(b), inv[b].erase(a);
for(auto it : adj[b]) {
inv[it].erase(b);
weak(a, it);
}
for(auto it : inv[b]) {
adj[it].erase(b);
weak(it, a);
}
}
int main() {
cin.tie()->sync_with_stdio(false);
int n, m;
cin >> n >> m;
for(int i = 1; i <= n; i++) {
sz[i] = 1, root[i] = i;
child[i].insert(i);
}
for(int i = 1; i <= m; i++) {
int a, b;
cin >> a >> b;
b = find(b);
if(find(a) != b && child[b].count(a) == 0) {
ans += sz[b];
child[b].insert(a);
a = find(a);
weak(a, b);
while(!q.empty()) {
pair<int, int> p = q.front();
q.pop();
unite(p.first, p.second);
}
}
cout << ans << '\n';
}
return 0;
}
