#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<ll, ll>
#define f first
#define s second
#define REP(i,n) for (int i = 0; i<n; ++i)
#define REP1(i,n) for (int i = 1; i<=n; ++i)
#define pb push_back
#define SZ(x) (int)((x).size())
#define ALL(x) (x).begin(), (x).end()
#define MX(a,b) a = max(a,b)
#define MN(a,b) a = min(a,b)
#ifdef BALBIT
template<typename T> void _do(T && x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T && x, S && ...y){cerr<<x<<", "; _do(y...);}
#define bug(...) cerr<<"#"<<__LINE__<<"- "<<#__VA_ARGS__<<": ", _do(__VA_ARGS__)
#else
#define bug(...)
#define endl '\n'
#endif // BALBIT
const int maxn = 1e5+5;
int par[maxn];
int sz[maxn];
set<int> here[maxn];
set<int> ing[maxn];
set<int> outg[maxn]; // which sets point out of me
set<int> intopt[maxn]; // which individual points point into me
int find(int x) {
return x == par[x]? x : par[x] = find(par[x]);
}
int re = 0;
queue<pii> tomerge;
void mrg(int A, int B){
A = find(A); B= find(B);
if (A == B) return;
bug(A,B);
re -= SZ(intopt[B]) * sz[B] + SZ(intopt[A]) * sz[A];
re -= (sz[B]) * (sz[B]-1) + (sz[A] * (sz[A]-1));
if (SZ(here[B]) < SZ(intopt[A])) {
for (int x : here[B]) {
if (intopt[A].count(x)) intopt[A].erase(x);
}
}else{
set<int> nset;
for( int x : intopt[A]) {
if (!here[B].count(x)) {
nset.insert(x);
}
}
intopt[A].swap(nset);
}
if (SZ(here[A]) < SZ(intopt[B])) {
for (int x : here[A]) {
if (intopt[B].count(x)) intopt[B].erase(x);
}
}else{
set<int> nset;
for( int x : intopt[B]) {
if (!here[A].count(x)) {
nset.insert(x);
}
}
intopt[B].swap(nset);
}
if (SZ(intopt[A]) + SZ(here[A]) + SZ(outg[A]) + SZ(ing[A]) > SZ(intopt[B]) + SZ(here[B]) + SZ(outg[B]) + SZ(ing[B])) {
swap(A,B); //swapped = 1;
}
// a into b
for (int x : intopt[A]) {
intopt[B].insert(x);
}
for (int x : here[A]) {
here[B].insert(x);
}
for (int x : outg[A]) {
if (x != B) {
outg[B].insert(x);
ing[x].erase(A); ing[x].insert(B);
if (ing[B].count(x)) {
bug("bruh? ", A, B, x);
tomerge.push({B,x});
}
}
}
for (int x : ing[A]) {
if (x != B) {
ing[B].insert(x);
outg[x].erase(A); outg[x].insert(B);
if (outg[B].count(x)) {
bug("yo? ", A, B, x);
tomerge.push({B,x});
}
}
}
outg[B].erase(A);
ing[B].erase(A);
sz[B] += sz[A];
par[A] = B;
bug(SZ(intopt[B]));
re += SZ(intopt[B]) * sz[B];
re += (sz[B] * (sz[B]-1));
bug(re);
}
void add(int a, int b) { // edge from A to B
int A = find(a), B = find(b);
if (A == B) return;
if (intopt[B].count(a)) return;
if (outg[B].count(A)) {
// merge sequence!
bool swapped = 0;
tomerge.push({A,B});
while (!tomerge.empty()) {
mrg(tomerge.front().f, tomerge.front().s);
tomerge.pop();
}
}else{
ing[B].insert(A);
outg[A].insert(B);
intopt[B].insert(a);
re += sz[B];
}
}
signed main(){
ios::sync_with_stdio(0), cin.tie(0);
bug(1,2);
int n,m; cin>>n>>m;
REP(i,n) {
par[i] = i; sz[i] = 1; here[i].insert(i);
}
REP(i,m) {
int a,b; cin>>a>>b; --a; --b;
add(a,b);
cout<<re<<endl;
}
}
