#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n, m;
ll cnt = 0;
vector<int> par;
vector<vector<int> > group;
vector<set<int> > group_edges;
vector<set<int> > group_followers;
vector<set<int> > person_following;
void add_edge(int a, int gb);
void add_group_edge (int ga, int gb) {
ga = par[ga];
gb = par[gb];
if(ga == gb) return;
if(group_edges[ga].count(gb)) return;
group_edges[ga].insert(gb);
if(group_edges[gb].count(ga)){
if(group[ga].size() < group[gb].size()) swap(ga, gb);
vector<pair<int,int> > add_edges;
while(!group_followers[gb].empty()){
int a = *group_followers[gb].begin();
cnt -= (int)group[gb].size();
group_followers[gb].erase(a);
person_following[a].erase(gb);
add_edges.push_back({a, gb});
}
for(int b : group[gb]){
while(!person_following[b].empty()){
int gc = *person_following[b].begin();
cnt -= (int)group[gc].size();
person_following[b].erase(gc);
group_followers[gc].erase(b);
add_edges.push_back({b, gc});
}
}
cnt -= 1ll * ((int)group[ga].size()) * ((int)group[ga].size() - 1);
cnt -= 1ll * ((int)group[gb].size()) * ((int)group[gb].size() - 1);
for(int x : group[gb]){
par[x] = ga;
group[ga].push_back(x);
}
cnt += 1ll * ((int)group[ga].size()) * ((int)group[ga].size() - 1);
cnt += 1ll * ((int)group_followers[ga].size()) * ((int)group[gb].size());
for(pair<int,int> x : add_edges){
add_edge(x.first, x.second);
}
}
}
void add_edge(int a, int b){
int ga = par[a];
int gb = par[b];
if(ga == gb) return;
if(person_following[a].count(gb)) return;
cnt += (int)group[gb].size();
person_following[a].insert(gb);
group_followers[gb].insert(a);
add_group_edge(ga, gb);
}
int main(){
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n >> m;
par.resize(n), group.resize(n), group_edges.resize(n);
group_followers.resize(n), person_following.resize(n);
for(int i = 0; i < n; i++){
par[i] = i;
group[i].push_back(i);
}
for(int i = 0; i < m; i++){
int a, b;
cin >> a >> b;
a--; b--;
add_edge(a, b);
cout << cnt << '\n';
}
}
