#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,m,U[301000],V[300100];ll ans[301000];
int fa[300100],sg[300100];
	int F(int x){if(x==fa[x])return x;return fa[x]=F(fa[x]);}
	void sol__(){
		for(int i=1;i<=n;i++)fa[i]=i;for(int i=1;i<n;i++)sg[i]=0;
		int c0=n-1,c1=0;
		for(int i=1;i<=m;i++){
			if(U[i]>V[i])swap(U[i],V[i]);
			int l=F(U[i]),r=F(V[i]);
			while(l!=r){
				if(sg[l]==0)c0--,c1++;else c1--;
				sg[l]++,l=F(l+1);
			}
			l=F(U[i]);
			while(l!=r){int fp=F(l+1);if(sg[l]==2)fa[l]=fp;l=fp;}
			ans[i]=1ll*c0*i+c1+1ll*c0*(n-1-c0);
		}
	}
#define pi pair<int,int>
#define mp make_pair
#define pb push_back
#define fi first
#define se second
int col[301000],pre[301000],nxt[301000],sz[1200100],sc;
	int k1[1201000],k2[1200100];
	ll ns;
	void build(int p,int l,int r){
		if(l==r){k1[p]=k2[p]=l;return;}
		int mid=(l+r)>>1;build(p<<1,l,mid),build(p<<1|1,mid+1,r); 
		k1[p]=(pre[k1[p<<1]]<pre[k1[p<<1|1]])?k1[p<<1]:k1[p<<1|1];
		k2[p]=(nxt[k2[p<<1]]>nxt[k2[p<<1|1]])?k2[p<<1]:k2[p<<1|1];
	}
	int ask1(int p,int l,int r,int x,int y){
		if(x<=l&&r<=y)return k1[p];
		int mid=(l+r)>>1;
		if(y<=mid)return ask1(p<<1,l,mid,x,y);
		if(x>mid)return ask1(p<<1|1,mid+1,r,x,y);
		int o1=ask1(p<<1,l,mid,x,y),o2=ask1(p<<1|1,mid+1,r,x,y);
		return (pre[o1]<pre[o2])?o1:o2;
	}
	int ask2(int p,int l,int r,int x,int y){
		if(x<=l&&r<=y)return k2[p];
		int mid=(l+r)>>1;
		if(y<=mid)return ask2(p<<1,l,mid,x,y);
		if(x>mid)return ask2(p<<1|1,mid+1,r,x,y);
		int o1=ask2(p<<1,l,mid,x,y),o2=ask2(p<<1|1,mid+1,r,x,y);
		return (nxt[o1]>nxt[o2])?o1:o2;
	}
	void up(int p,int l,int r,int x){
		if(l==r){k1[p]=k2[p]=l;return;}
		int mid=(l+r)>>1;if(x<=mid)up(p<<1,l,mid,x);else up(p<<1|1,mid+1,r,x);
		k1[p]=(pre[k1[p<<1]]<pre[k1[p<<1|1]])?k1[p<<1]:k1[p<<1|1];
		k2[p]=(nxt[k2[p<<1]]>nxt[k2[p<<1|1]])?k2[p<<1]:k2[p<<1|1];
	}
	ll C2(ll x){return x*(x-1)/2;}
	void cut1(pi l,pi r){
		nxt[l.se]=r.se,pre[r.se]=l.se;
		up(1,1,n,l.se),up(1,1,n,r.se);
		int co=col[l.fi],S=sz[co],s2=0;
		for(int i=l.fi;i!=r.fi;i=nxt[i]){s2++;if(s2*2>S)break;}
		s2++,sc++;
		if(s2*2<=S){
			sz[co]=S-s2,sz[sc]=s2;
			for(int i=l.fi;i!=r.fi;i=nxt[i])col[i]=sc;col[r.fi]=sc;
		}
		else{
			s2=0;
			for(int i=l.se;i!=n+1;i=pre[i])col[i]=sc,s2++;
			for(int i=r.se;i;i=nxt[i])col[i]=sc,s2++;
			sz[co]=S-s2,sz[sc]=s2;
		}
		ns-=C2(S),ns+=C2(sz[co]),ns+=C2(sz[sc]);
	}
	void cut2(pi x){
		nxt[x.se]=0,up(1,1,n,x.se);
		int co=col[x.fi],S=sz[co],s2=0;
		for(int i=x.fi;i;i=nxt[i]){s2++;if(s2*2>S)break;}
		sc++;
		if(s2*2<=S){
			sz[co]=S-s2,sz[sc]=s2;
			for(int i=x.fi;i;i=nxt[i])col[i]=sc;
		}
		else{
			s2=0;for(int i=x.se;i!=n+1;i=pre[i])col[i]=sc,s2++;
			sz[co]=S-s2,sz[sc]=s2;
		}
		ns-=C2(S),ns+=C2(sz[co]),ns+=C2(sz[sc]);
	}
	void cut3(pi x){
		pre[x.se]=n+1,up(1,1,n,x.se);
		int co=col[x.fi],S=sz[co],s2=0;
		for(int i=x.fi;i!=n+1;i=pre[i]){s2++;if(s2*2>S)break;}
		sc++;
		if(s2*2<=S){
			sz[co]=S-s2,sz[sc]=s2;
			for(int i=x.fi;i!=n+1;i=pre[i])col[i]=sc;
		}
		else{
			s2=0;for(int i=x.se;i;i=nxt[i])col[i]=sc,s2++;
			sz[co]=S-s2,sz[sc]=s2;
		}
		ns-=C2(S),ns+=C2(sz[co]),ns+=C2(sz[sc]);
	}
	int ob[300100];
	void sol_(){
		n--;
		ns=C2(n);
		for(int i=1;i<=n;i++)col[i]=1;sz[1]=n;
		sc=1;
		for(int i=1;i<n;i++)pre[i+1]=i,nxt[i]=i+1;pre[1]=n+1,nxt[n]=0;
		build(1,1,n);
		for(int i=1;i<=m;i++){
			if(U[i]>V[i])swap(U[i],V[i]);if(U[i]==V[i]){
			ans[i]+=ns;continue;};V[i]--;
			vector<pi>o1,o2;
			while(1){
				int sb=ask1(1,1,n,U[i],V[i]),pr=pre[sb];
				up(1,1,n,sb);
				if(pr>=U[i])break;
				o1.pb(mp(sb,pr)),pre[sb]=n+1;
			}
			while(1){
				int sb=ask2(1,1,n,U[i],V[i]),nx=nxt[sb];
				up(1,1,n,sb);
				if(nx<=V[i])break;
				o2.pb(mp(sb,nx)),nxt[sb]=0;
			}
			sort(o1.begin(),o1.end(),[&](pi x,pi y){return col[x.fi]<col[y.fi];}),
			sort(o2.begin(),o2.end(),[&](pi x,pi y){return col[x.fi]<col[y.fi];});
			int i1=0,i2=0;
			while(i1<(int)o1.size()&&i2<(int)o2.size()){
				if(col[o1[i1].fi]==col[o2[i2].fi])cut1(o1[i1],o2[i2]),i1++,i2++;
				else if(col[o1[i1].fi]<col[o2[i2].fi])cut2(o1[i1]),i1++;
				else cut3(o2[i2]),i2++;
			}
			while(i1<(int)o1.size())cut2(o1[i1]),i1++;
			while(i2<(int)o2.size())cut3(o2[i2]),i2++;
			ans[i]+=ns;
		}
	}
void sol(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)scanf("%d%d",&U[i],&V[i]),ans[i]=0;
	if(n==1){for(int i=1;i<=m;i++)puts("0");return;}
	sol__();
	sol_();
	for(int i=1;i<=m;i++)printf("%lld\n",ans[i]);
}
int main(){
	int T;scanf("%d",&T);while(T--)sol();
	return 0;
}