#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,popcnt")
#define int long long
#define f first
#define s second
using namespace std;
int mod = 1e9 + 7;
int ans = 0;
queue<pair<int, int>> q;
vector<set<int>> t, f, c;
struct DSU {
vector<int> e;
DSU(int N) {e = vector<int>(N, -1);}
int get(int x) {return e[x] < 0 ? x : e[x] = get(e[x]);}
bool same_set(int a, int b) {return get(a) == get(b);}
int size(int x) {
x = get(x);
return c[x].size() + t[x].size() + f[x].size();
}
int dsu_size(int x) {
x = get(x);
return -e[x];
}
void erase(int x, int y) {
t[x].erase(y);
t[y].erase(x);
f[x].erase(y);
f[y].erase(x);
}
void insert(int x, int y) {
t[x].insert(y);
f[y].insert(x);
if (t[y].count(x)) q.push({x, y});
}
void unite(int x, int y) {
x = get(x);
y = get(y);
if (x == y) return;
if (size(x) < size(y)) swap(x,y);
ans += c[x].size() * (-e[y]) + c[y].size() * (-e[x]);
e[x] += e[y];
e[y] = x;
erase(x, y);
for (int i : c[y]) {
if (c[x].count(i)) ans += e[x];
else c[x].insert(i);
}
for (int i : t[y]) {
f[i].erase(y);
insert(x, i);
}
for (int i : f[y]) {
t[i].erase(y);
insert(i, x);
}
}
};
void solve() {
int n, m;
cin >> n >> m;
t.resize(n + 1);
f.resize(n + 1);
c.resize(n + 1);
for (int i = 1; i <= n; i++) c[i].insert(i);
DSU dsu(n + 1);
while (m--) {
int a, b;
cin >> a >> b;
b = dsu.get(b);
if (dsu.get(a) != b && !c[b].count(a)) {
c[b].insert(a);
ans += dsu.dsu_size(b);
a = dsu.get(a);
dsu.insert(a, b);
while (!q.empty()) {
pair<int, int> k = q.front();
q.pop();
dsu.unite(k.f, k.s);
}
}
cout << ans << "\n";
}
}
int32_t main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
solve();
return 0;
}
