#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define i128 __int128
#define mem(x) memset(x,0,sizeof(x))
#define endl "\n"
#define printYes cout << "Yes\n"
#define printYES cout << "YES\n"
#define printNo cout << "No\n"
#define printNO cout << "NO\n"
#define lowbit(x) ((x)&(-(x)))
#define pb push_back
#define mkp make_pair
#define pii pair<int,int>
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define rep(i,j,k) for (int i=(j);i<=(k);i++)
#define per(i,j,k) for (int i=(j);i>=(k);i--)
#define pcnt(x) __builtin_popcount(x)
mt19937_64 rnd(time(0));
template<class T>void chkmin(T&x,T y){x=min(x,y);}
template<class T>void chkmax(T&x,T y){x=max(x,y);}

const ll inf=1000000000000000000; 
//const ll inf=1000000000;
//const ll mod=998244353;
//const ll mod=1000000007;

const int N=400005;
int n,m; 
int a[N],b[N];
int fa[N],c[N],d[N],num[N];
ll ans[N],ansb[N];
int find(int x)
{
	if (x==fa[x]) return x;
	return fa[x]=find(fa[x]);
}
void assign(int l,int r,int x)
{
	l=find(l);
	while (l<r)
	{
		if (c[l]==0) c[l]=x;
		else
		{
			d[l]=x;
			fa[l]=l+1;
		}
		l=find(l+1);
	}
}
set<int>s[N],p[N];
int mx[N*4],mn[N*4];
inline void push_up(int u)
{
	mx[u]=max(mx[u*2],mx[u*2+1]);
	mn[u]=min(mn[u*2],mn[u*2+1]);
}
void update(int u,int l,int r,int x)
{
	if (l==r)
	{
		if (SZ(s[l])==0) mx[u]=0;
		else mx[u]=*s[l].rbegin();
		if (SZ(p[l])==0) mn[u]=1e9;
		else mn[u]=*p[l].begin();
		return;
	}
	int mid=(l+r)>>1;
	if (x<=mid) update(u*2,l,mid,x);
	else update(u*2+1,mid+1,r,x);
	push_up(u);
}
int querymax(int u,int L,int R,int l,int r)
{
	if (l>r) return 0;
	if (l<=L&&R<=r) return mx[u];
	int mid=(L+R)>>1;
	int res=0;
	if (l<=mid) chkmax(res,querymax(u*2,L,mid,l,r));
	if (mid<r) chkmax(res,querymax(u*2+1,mid+1,R,l,r));
	return res;
}
int querymin(int u,int L,int R,int l,int r)
{
	if (l>r) return 1e9;
	if (l<=L&&R<=r) return mn[u];
	int mid=(L+R)>>1;
	int res=1e9;
	if (l<=mid) chkmin(res,querymin(u*2,L,mid,l,r));
	if (mid<r) chkmin(res,querymin(u*2+1,mid+1,R,l,r));
	return res;
}
void add(int x,int y)
{
	//cerr << "add " << x << " " << y << endl;
	s[x].insert(y),p[y].insert(x);
	update(1,1,n-1,x);
	update(1,1,n-1,y);
}
void del(int x,int y)
{
	//cerr << "del " << x << " " << y << endl;
	s[x].erase(y),p[y].erase(x);
	update(1,1,n-1,x);
	update(1,1,n-1,y);
}

int rt[N*2],cnt;
ll res;

namespace treap
{
	int tot=0;
	struct node
	{
	    int val,rnk,l,r,size,mx,mn,fa;
	}tree[N];
	inline void update(int u)
	{
		tree[u].fa=0;
		if (tree[u].l) tree[tree[u].l].fa=u;
		if (tree[u].r) tree[tree[u].r].fa=u;
		tree[u].size=tree[tree[u].l].size+tree[tree[u].r].size+1;
		tree[u].mx=max({tree[tree[u].l].mx,tree[tree[u].r].mx,tree[u].val});
		tree[u].mn=min({tree[tree[u].l].mn,tree[tree[u].r].mn,tree[u].val});
	}
	int make_node(int val) 
	{
	    tree[++tot].size=1;
	    tree[tot].val=val;
	    tree[tot].mx=tree[tot].mn=val;
	    tree[tot].l=tree[tot].r=0;
	    tree[tot].rnk=rand();
	    return tot;
	}
	void split(int u,int val,int &x,int &y)
	{
		if (u==0)
		{
			x=y=0;
			return;
		}
		if (tree[u].val<=val) 
		{
			x=u;
			split(tree[u].r,val,tree[u].r,y);
		}
		else
		{
			y=u;
			split(tree[u].l,val,x,tree[u].l);
		}
		update(u);
	}
	void merge(int &u,int x,int y)
	{
		if (x==0||y==0)
		{
			u=x+y;
			return;
		}
		if (tree[x].rnk<tree[y].rnk)
		{
			u=x;
			merge(tree[u].r,tree[x].r,y);
		}
		else
		{
			u=y;
			merge(tree[u].l,x,tree[y].l);
		}
		update(u);
	}
	void insert(int &u,int val)
	{
		int x=0,y=0;
		split(u,val,x,y);
		merge(x,x,make_node(val));
		merge(u,x,y);
	}
	int ask(int u)
	{
		if (tree[u].fa) return ask(tree[u].fa);
		return u;
	}
	void init()
	{
		tree[0].mn=1e9;
		rep(i,1,n-1) insert(rt[1],i);
		rep(i,1,n-2) add(i,i+1);
		res=1ll*(n-1)*(n-2)/2;
	}
	void split(int u,int l,int r)
	{
		//cerr << u << " " << l << " " << r << endl;
		if (tree[u].mn<l&&tree[u].mx>r)
		{
			res-=1ll*(tree[u].size-1)*tree[u].size/2;
			int x,y,z;
			split(u,l-1,x,y);
			split(y,r,y,z);
			del(tree[x].mx,tree[y].mn);
			del(tree[y].mx,tree[z].mn);
			add(tree[x].mx,tree[z].mn);
			merge(x,x,z);
			res+=1ll*(tree[x].size-1)*tree[x].size/2;
			res+=1ll*(tree[y].size-1)*tree[y].size/2;
		}
		else if (tree[u].mn<l&&tree[u].mx>=l)
		{
			res-=1ll*(tree[u].size-1)*tree[u].size/2;
			int x,y;
			split(u,l-1,x,y);
			del(tree[x].mx,tree[y].mn);
			res+=1ll*(tree[x].size-1)*tree[x].size/2;
			res+=1ll*(tree[y].size-1)*tree[y].size/2;
		}
		else if (tree[u].mn<=r&&tree[u].mx>r)
		{
			//cerr << u << " " << l << " " << r << endl;
			res-=1ll*(tree[u].size-1)*tree[u].size/2;
			int x,y;
			split(u,r,x,y);
			del(tree[x].mx,tree[y].mn);
			res+=1ll*(tree[x].size-1)*tree[x].size/2;
			res+=1ll*(tree[y].size-1)*tree[y].size/2;
		}
	}
}

void update(int l,int r)
{
	while (1)
	{
		int w=querymin(1,1,n-1,l,r);
		if (w>=l) break;
		int id=treap::ask(w);
		treap::split(id,l,r);
	}
	while (1)
	{
		int w=querymax(1,1,n-1,l,r);
		if (w<=r) break;
		int id=treap::ask(w);
		treap::split(id,l,r);
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin >> n >> m;
	rep(i,1,m)
	{
		cin >> a[i] >> b[i];
		if (a[i]>b[i]) swap(a[i],b[i]);
	}
	rep(i,1,n+1) fa[i]=i;
	rep(i,1,m) assign(a[i],b[i],i);
	rep(i,1,n-1) 
	{
		int v=m;
		if (c[i]) v=c[i]-1;
		num[v]++;
	}
	per(i,m,1) num[i]+=num[i+1];
	rep(i,1,m) ans[i]+=1ll*num[i]*(n-1+i-num[i]);
	rep(i,1,n-1) 
	{
		if (c[i]==0) continue;
		int l=c[i],r=m;
		if (d[i]) r=d[i]-1;
		ansb[l]++,ansb[r+1]--;
	}
	treap::init();
	rep(i,1,m)
	{
		int l=a[i],r=b[i]-1;
		if (l<=r) update(l,r);
		ans[i]+=res;
	}
	rep(i,1,m) ansb[i]+=ansb[i-1];
	rep(i,1,m) cout << ans[i]+ansb[i] << endl;
	return 0;
}