#include<bits/stdc++.h>
using namespace std;
mt19937 rnd(time(0));
inline int read(){
    int x=0;
    char c;
    while(c=getchar())if(c>='0'&&c<='9')break;
    while(c>='0'&&c<='9'){
        x=(x<<3)+(x<<1)+c-'0';
        c=getchar();
    }
    return x;
}
const int N=500005;
#define ull unsigned long long
int T,n,m,rt[N],tot,a[N],X[N],Y[N];
ull v[N];
struct tree{
    int son[2];
    long long sum;
}tr[N*100];
inline void update(int &k,int l,int r,int x){
    ++tot;
    tr[tot]=tr[k];
    tr[tot].sum^=v[x];
    k=tot;
    if(l==r)return;
    int mid=(l+r)>>1;
    if(x<=mid)update(tr[k].son[0],l,mid,x);
    else update(tr[k].son[1],mid+1,r,x);
}
inline int lcp(int l,int r,int a,int b){
    if(l==r){
        if(tr[a].sum^tr[b].sum)return 0;
        return l;
    }
    int mid=(l+r)>>1;
    if(tr[tr[a].son[0]].sum^tr[tr[b].son[0]].sum)return lcp(l,mid,tr[a].son[0],tr[b].son[0]);
    return max(mid,lcp(mid+1,r,tr[a].son[1],tr[b].son[1]));
}
inline bool cmp(int x,int y){
    int LCP=lcp(0,m,rt[x],rt[y]);
    if(LCP==m)return x<y;
    if(Y[LCP+1]>=x&&X[LCP+1]<x)return 0;
    return 1;
}
pair<int,int>b[N]; 
struct node{
    int a,b;
    inline friend node operator + (node x,node y){
        if(x.a==y.a)return (node){x.a,x.b+y.b};
        if(x.a<y.a)return x;
        return y;
    }
};
node minn[N<<2],sec[N<<2];
int lazy[N<<2];
inline void build(int k,int l,int r){
    minn[k].a=0,minn[k].b=r-l+1,sec[k].a=1,sec[k].b=0,lazy[k]=0;
    if(l==r)return;
    int mid=(l+r)>>1;
    build(k<<1,l,mid),build(k<<1|1,mid+1,r);
}
inline void pushup(int k){
    minn[k]=minn[k<<1]+minn[k<<1|1];
    if(minn[k<<1].a<minn[k<<1|1].a)sec[k]=sec[k<<1]+minn[k<<1|1];
    else if(minn[k<<1].a==minn[k<<1|1].a)sec[k]=sec[k<<1]+sec[k<<1|1];
    else sec[k]=minn[k<<1]+sec[k<<1|1]; 
}
inline void pd(int k,int x){
    minn[k].a+=x,sec[k].a+=x,lazy[k]+=x;
} 
inline void pushdown(int k){
    if(lazy[k]){
        pd(k<<1,lazy[k]),pd(k<<1|1,lazy[k]);
        lazy[k]=0;
    }
}
inline void update(int k,int l,int r,int x,int y){
	if(x>y)return;
    if(l>=x&&r<=y){
        pd(k,1);
        return;
    }
    pushdown(k);
    int mid=(l+r)>>1;
    if(x<=mid)update(k<<1,l,mid,x,y);
    if(y>=mid+1)update(k<<1|1,mid+1,r,x,y);
    pushup(k);
}
set<pair<int,int> >s;
vector<int>ve[N];
int main(){
    T=read();
    while(T--){
        n=read(),m=read();
        for(int i=1;i<=n;++i)ve[i].clear();
        int x,y;
        for(int i=1;i<=m;++i){
            x=X[i]=read(),y=Y[i]=read();
            if(X[i]>Y[i])swap(X[i],Y[i]);
            v[i]=(ull)rnd()*(ull)rnd();
            ve[x+1].push_back(i),ve[y+1].push_back(i);
        }
        tot=0;
        for(int i=1;i<=n;++i){
            rt[i]=rt[i-1];
            for(int j=0;j<ve[i].size();++j)update(rt[i],0,m,ve[i][j]);
        }
        for(int i=1;i<n;++i)a[i]=i+1;
        sort(a+1,a+n,cmp);
        //for(int i=2;i<=n;++i){
        	//for(int j=2;j<=n;++j)cout<<lcp(0,m,rt[i],rt[j])<<' ';
        	//cout<<endl;
		//}
        //for(int i=1;i<n;++i)cout<<a[i]<<' ';
        //cout<<endl;
        int num=0;
        for(int i=1;i<n-1;++i)b[++num]={lcp(0,m,rt[a[i]],rt[a[i+1]]),i};
        sort(b+1,b+num+1);
        build(1,2,n);
        s.clear();
        s.insert({1,n-1});
        int now=0;
        long long res=1ll*(n-1)*(n-2)/2ll; 
        for(int i=1;i<=m;++i){
            update(1,2,n,X[i]+1,Y[i]);
            long long ans=0;
            if(minn[1].a==0){
                ans+=1ll*minn[1].b*(n+i-2)-1ll*minn[1].b*(minn[1].b-1);
                if(sec[1].a==1){
                    ans+=sec[1].b;
                }
            }
            else if(minn[1].a==1){
                ans+=minn[1].b;
            }
            //cout<<ans<<' ';
            while(now<num&&b[now+1].first<i){
                ++now;
                int x=b[now].second;
                auto it=s.upper_bound({x,n+1});
                --it;
                int l=(*it).first,r=(*it).second;
                res-=1ll*(r-l+1)*(r-l)/2ll;
                s.erase(it);
                s.insert({l,x}),s.insert({x+1,r});
                res+=1ll*(x-l+1)*(x-l)/2ll+1ll*(r-x)*(r-x-1)/2ll;
            }
            //cout<<s.size()<<' ';
            ans+=res;
            printf("%lld\n",ans);
        }
    }
}