#include <bits/stdc++.h>
using namespace std;
#ifdef MIKU
#define debug(x...) cout << '[' << #x << "] : ", dout(x)
void dout() { cout << endl; }
template <typename T, typename ...U>
void dout(T t, U ...u) { cout << t << (sizeof...(u) ? ", " : ""); dout(u...); }
#else
#define debug(...) 39
#endif
#define int long long
#define fs first
#define sc second
#define mp make_pair
#define FOR(i, j, k) for (int i = j, Z = k; i < Z; i++)
typedef pair<int, int> pii;
const int MXN = 100005;
int n, m;
struct DSU {
int p[MXN];
void init(int n) {
fill(p + 1, p + n + 1, -1);
}
int find(int x) {
return (p[x] < 0 ? x : p[x] = find(p[x]));
}
bool onion(int x, int y) {
x = find(x);
y = find(y);
if (x == y) return false;
p[y] += p[x];
p[x] = y;
return true;
}
};
namespace DS {
DSU dsu;
int deg_in[MXN], deg_out[MXN];
queue<pii> q;
set<pii> out[MXN];
unordered_map<int, vector<int>> M[MXN];
set<int> S[MXN];
int ansE = 0, ansG = 0;
int tri(int x) {
return x * (x - 1);
}
int SIZE(int X) {
return -dsu.p[X];
}
void init(int n) {
dsu.init(n);
}
void ADD_EDGE(int x, int X, int Y) {
deg_in[Y]++;
deg_out[X]++;
out[X].insert(mp(x, Y));
M[Y][X].push_back(x);
S[x].insert(Y);
ansE += SIZE(Y);
// debug('+', x, Y, ansE);
}
void ERASE_EDGE(int x, int X, int Y) {
deg_out[X]--;
deg_in[Y]--;
out[X].erase(mp(x, Y));
S[x].erase(Y);
ansE -= SIZE(Y);
// debug('-', x, Y, ansE);
}
void MERGE(int X, int Y) {
ansG -= tri(SIZE(X));
ansG -= tri(SIZE(Y));
ansG += tri(SIZE(X) + SIZE(Y));
for (auto &i : M[X][Y]) ERASE_EDGE(i, Y, X);
M[X].erase(Y);
for (auto &i : M[Y][X]) ERASE_EDGE(i, X, Y);
M[Y].erase(X);
if (deg_in[X] + deg_out[X] >= deg_in[Y] + deg_out[Y]) swap(X, Y);
// debug("MERGE", X, Y);
{
for (auto it = M[X].begin(); it != M[X].end(); it++) {
for (auto &i : it -> sc) {
ERASE_EDGE(i, dsu.find(i), X);
q.push(mp(i, Y));
}
}
M[X].clear();
}
{
vector<pii> v;
for (auto i : out[X]) v.push_back(i);
for (auto i : v) {
ERASE_EDGE(i.fs, X, i.sc);
q.push(mp(i.fs, i.sc));
}
for (auto i : v) {
M[i.sc][X].clear();
}
out[X].clear();
// debug("CLEAR", X);
}
ansE -= SIZE(Y) * deg_in[Y];
dsu.onion(X, Y);
ansE += SIZE(Y) * deg_in[Y];
}
void TEST(int x, int Y) {
if (S[x].find(Y) != S[x].end()) return;
int X = dsu.find(x);
auto it = M[X].find(Y);
if (it == M[X].end() || it -> sc.empty()) {
ADD_EDGE(x, X, Y);
return;
}
MERGE(X, Y);
}
void clear_queue() {
while (q.size()) {
auto [x, y] = q.front();
q.pop();
if (dsu.find(x) == dsu.find(y)) continue;
TEST(x, dsu.find(y));
}
}
void COUT() {
cout << endl;
FOR(i, 1, n + 1) {
cout << i << ": ";
// for (auto j : S[i]) cout << j << ' ';
for (auto it = M[i].begin(); it != M[i].end(); it++) {
cout << '[' << it -> fs << ":";
for (auto &j : it -> sc) cout << ' ' << j;
cout << "] ";
}
cout << endl;
}
debug(ansE, ansG);
cout << endl;
}
}
void miku() {
int a, b;
cin >> n >> m;
// cin >> n;
DS::init(n);
while (m--) {
cin >> a >> b;
// while (cin >> a >> b) {
DS::q.push(mp(a, b));
DS::clear_queue();
// DS::COUT();
cout << DS::ansE + DS::ansG << '\n';
// for (auto &i : DS::out[5]) cout << '<' << i.fs << ' ' << i.sc << "> ";
// cout << endl;
}
}
int32_t main() {
cin.tie(0) -> sync_with_stdio(false);
// cin.exceptions(iostream::failbit);
miku();
return 0;
}
