#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 10;
int n, par[maxn], m;
int sz[maxn];
int find_leader(int v)
{
if (par[v] == v)
return v;
return (par[v] = find_leader(par[v]));
}
set < int > rem;
set < int > adj[maxn];
set < int > rev_adj[maxn], child[maxn];
ll ans;
queue < pair < int, int > > to_merge;
void insert_weak_connection(int a, int b)
{
adj[a].insert(b);
rev_adj[b].insert(a);
if (adj[b].count(a))
to_merge.push({a, b});
}
void unite(int v, int u)
{
if (v == u)
return;
if (child[v].size() < child[u].size())
swap(v, u);
ans = ans + (ll)(child[v].size()) * sz[u] + (ll)(child[u].size()) * sz[v];
par[u] = v;
sz[v] += sz[u];
for (int d : child[u])
{
if (child[v].count(d)) ans -= sz[v];
else
child[v].insert(d);
}
adj[v].erase(u);
adj[u].erase(v);
rev_adj[v].erase(u);
rev_adj[u].erase(v);
for (int d : adj[u])
{
rev_adj[d].erase(u);
insert_weak_connection(v, d);
}
for (int d : rev_adj[u])
{
adj[d].erase(u);
insert_weak_connection(d, v);
}
}
void solve()
{
cin >> n >> m;
for (int i = 1; i <= n; i ++)
{
par[i] = i;
sz[i] = 1;
child[i].insert(i);
}
for (int i = 1; i <= m; i ++)
{
int v, u;
cin >> v >> u;
u = find_leader(u);
if (find_leader(v) != u && !child[u].count(v))
{
child[u].insert(v);
ans += sz[u];
v = find_leader(v);
insert_weak_connection(v, u);
while(to_merge.size())
{
pair < int, int > cur = to_merge.front();
to_merge.pop();
unite(find_leader(cur.first), find_leader(cur.second));
}
}
cout << ans << endl;
}
}
int main()
{
solve();
return 0;
}
/**
5 20
4 2
1 5
2 3
2 5
3 2
3 1
4 5
1 2
10 18
10 6
7 8
8 4
9 3
2 8
9 2
1 10
1 8
8 9
5 6
2 10
4 3
7 2
10 2
10 5
3 7
1 9
8 7
1 2
9 1
7 6
9 7
10 3
8 3
6 3
7 5
8 2
6 1
4 9
7 1
4 2
6 8
7 3
9 8
5 1
10 4
6 4
1 4
6 7
3 1
9 10
3 2
1 7
2 5
10 1
2 7
2 1
5 8
7 9
2 4
6 9
3 8
10 7
8 5
5 4
8 6
5 10
3 5
5 7
8 1
4 7
4 1
10 8
9 5
4 8
6 10
1 6
2 9
1 5
6 5
3 9
4 10
2 3
5 2
1 3
4 6
2 6
8 10
3 10
4 5
3 6
9 4
5 3
9 6
6 2
7 10
3 4
5 9
10 9
7 4
*/
