#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
#include <queue>
#include <deque>
#include <iomanip>
#include <cmath>
#include <set>
#include <stack>
#include <map>
#include <unordered_map>
#define FOR(i,n) for(int i=0;i<n;i++)
#define FORE(i,a,b) for(int i=a;i<=b;i++)
#define ll long long
#define ld long double
//#define int short
#define vi vector<int>
#define pb push_back
#define ff first
#define ss second
#define ii pair<int,int>
#define iii pair<int,ii>
#define pll pair<ll,ll>
#define plll pair<ll,pll>
#define mp make_pair
#define vv vector
#define endl '\n'
using namespace std;
/*
1) when merging two cliques of size A and B, we need to add A*B-1 edges.
*/
const int MAXN = 1e5+5;
int D = 0;
int E = 0;
int F = 0;
int G = 0;
struct DSU{
int tot = 0;
int parent[MAXN];
set<int> incoming[MAXN];// individual nodes
set<int> incomingCliques[MAXN];
set<int> allIncomers;
set<ii> outgoing[MAXN];//
int sz[MAXN];
DSU(){
FOR(i,MAXN)parent[i] = i;
//FOR(i,MAXN)incoming[i] = new set<int>(), outgoing[i] = new set<ii>();
FOR(i,MAXN)sz[i] = 1;
}
int find(int a){
if(a != parent[a])parent[a] = find(parent[a]);
return parent[a];
}
bool isSame(int a,int b){
return find(a) == find(b);
}
// outgoing[e] = {a,i} means there are i edges going from Supernodes e to a
// we only keep track of outgoing edges + internal clique edges;
inline void addEdge(int a,int b){
b = find(b);
incomingCliques[b].insert(find(a));
incoming[b].insert(a);
tot += sz[b];
}
void makeParent(int pa,int pb){
// make pa parent
allIncomers.clear();
if(F)cout << "tot : " << tot << endl;
if(G){
cout << pa << " <> " << pb << endl;
for(auto e: incoming[pa])cout << e << " ";cout << endl;
for(auto e: incoming[pb])cout << e << " ";cout << endl;
}
for(auto e : incoming[pa]){
if(find(e) != pb)
allIncomers.insert(e);
tot -= sz[pa];
}
for(auto e : incoming[pb]){
if(find(e) != pa)
allIncomers.insert(e);
tot -=sz[pb];
}
incoming[pa].clear();
incoming[pb].clear();
incomingCliques[pa].clear();
incomingCliques[pb].clear();
// destroyed all incoming edges. Now, we will add them back.
if(F)cout << "tot : " << tot << endl;
}
void merge(int a,int b){
if(isSame(a,b))return;
int pa = find(a);
int pb = find(b);
tot += 2*sz[pa]*sz[pb]; // new internal edges of the clique.
if(sz[a] > sz[b]){
makeParent(pa,pb);
parent[pb] = pa;
sz[pa] += sz[pb];
}else{
makeParent(pb,pa);
parent[pa] = pb;
sz[pb] += sz[pa];
}
for(auto e : allIncomers){
//cout << sz[b];
//cout << "EDGE ADDED EXPLICITLY: " << e << endl;
addEdge(e,pa);
}
}
void handleEdge(int a,int b){
int pa = find(a);
int pb = find(b);
// edge is a-> b
if(incoming[pb].find(a) != incoming[pb].end())return;
if(incomingCliques[pa].find(pb) != incomingCliques[pa].end()){
//need to merge cliques
if(E)cout << "NEED TO MERGE" << endl;
merge(a,b);
}else{
addEdge(a,b);
}
}
};
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n,m;
cin >> n >> m;
DSU dsu;
FOR(i,m){
int a,b;
cin >> a >> b;
a--;b--;
dsu.handleEdge(a,b);
cout << dsu.tot << endl;
}
return 0;
}
