#include <bits/stdc++.h>
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define EB emplace_back
#define V vector
#define ALL(v) (v).begin(), (v).end()
#define debug(x) cerr << "LINE(" << __LINE__ << ") ->" << #x << " is " << x << endl
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;
const int INF = 1e9 + 7, N = 1e5 + 7;
unordered_set<int> G[N], rG[N], ch[N];
int p[N], sz[N];
queue<pi> q;
ll ans = 0;
int find(int u) {
return p[u] == u ? u : p[u] = find(p[u]);
}
void add_edge(int u, int v) {
G[u].insert(v);
rG[v].insert(u);
if(G[v].count(u)) {
q.push({u, v});
}
}
int get_size(int u) {
return G[u].size() + rG[u].size() + ch[u].size();
}
void unite(int x, int y) {
x = find(x), y = find(y);
if(x == y) return;
if(get_size(x) > get_size(y)) swap(x, y);
ans += (ll) sz[x] * ch[y].size() + (ll) sz[y] * ch[x].size();
p[x] = y;
sz[y] += sz[x];
// merge x into y
for(int i:ch[x]) {
if(ch[y].count(i)) ans -= sz[y];
else ch[y].insert(i);
}
G[x].erase(y), G[y].erase(x);
rG[x].erase(y), rG[y].erase(x);
for(int i:G[x]) {
G[y].insert(i);
add_edge(y, i);
}
for(int i:rG[x]) {
rG[y].insert(i);
add_edge(i, y);
}
}
signed main()
{
ios::sync_with_stdio(0), cin.tie(0);
int n, m;
cin >> n >> m;
for(int i = 1; i <= n; i++) {
p[i] = i, sz[i] = 1;
ch[i].insert(i);
}
for(int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
v = find(v);
if(find(u) != v && ch[v].count(u) == 0) {
ch[v].insert(u);
ans += sz[v]; // u will connect to everyone in v's component
u = find(u);
add_edge(u, v);
while(q.size()) {
pi p = q.front(); q.pop();
unite(p.F, p.S);
}
}
cout << ans << '\n';
}
}
