#include<bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f3fll
#define debug(x) cerr<<#x<<"="<<x<<endl
using namespace std;
using ll=long long;
using ld=long double;
using pli=pair<ll,int>;
using pi=pair<int,int>;
template<typename A>
using vc=vector<A>;
inline int read()
{
    int s=0,w=1;char ch;
    while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    return s*w;
}
inline ll lread()
{
    ll s=0,w=1;char ch;
    while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    return s*w;
}
int L[5000001];
int R[5000001];
int ls[5000001];
int rs[5000001];
int fa[5000001];
int c[5000001];
set<int>S0,S1,nod;
ll ans;
int n,m,cnt;
inline void clear()
{
    S0.clear(),S1.clear(),nod.clear();
}
inline void cover(int l,int r)
{
    auto it=S1.lower_bound(l);
    while(it!=S1.end()&&*it<r) S1.erase(it),it=S1.lower_bound(l);
    
    it=S0.lower_bound(l);
    while(it!=S0.end()&&*it<r) S1.insert(*it),S0.erase(it),it=S0.lower_bound(l);
}
inline void push_up(int p)
{
    c[p]=c[ls[p]]+c[rs[p]];
    L[p]=min(L[ls[p]],L[rs[p]]);
    R[p]=max(R[ls[p]],R[rs[p]]);
    if(ls[p]) fa[ls[p]]=p;
    if(rs[p]) fa[rs[p]]=p;
}
inline ll run(int p)
{
    return (ll)c[p]*(c[p]-1)/2;
}
void split(int p,int pl,int pr,int l,int r,int &x,int &y)
{
    // printf("split %d %d %d %d %d\n",p,pl,pr,l,r);
    if(!p){ x=y=0;return ;}
    if(l<=L[p]&&R[p]<=r){ x=p,y=0;return ;}
    if(R[p]<l||r<L[p]){ x=0,y=p;return ;}
    int mid=(pl+pr)>>1;
    int L1,R1,L2,R2;
    split(ls[p],pl,mid,l,r,L1,L2);
    split(rs[p],mid+1,pr,l,r,R1,R2);
    if(!L1&&!R1){ x=0,y=p;return ;}
    if(!L2&&!R2){ x=p,y=0;return ;}
    x=p,ls[x]=L1,rs[x]=R1;
    y=++cnt,ls[y]=L2,rs[y]=R2,fa[y]=0;
    push_up(x),push_up(y);
}
inline bool check(int id)
{
    if(id==1||id==n) return false;
    if(nod.find(id)!=nod.end()) return false;
    nod.insert(id);
    return true;
}
inline int get(int u)
{
    while(fa[u]) u=fa[u];
    return u;
}
inline void edge()
{
    // for(int i=1;i<=cnt;i++) printf("%d : c=%d ls=%d rs=%d fa=%d L=%d R=%d\n",i,c[i],ls[i],rs[i],fa[i],L[i],R[i]);
    int u=read(),v=read();
    if(u==v) return ;
    if(u>v) swap(u,v);

    cover(u,v);
    if(check(u)){ int pu=get(u),x,y;ans-=run(pu);split(pu,1,n-1,u,v-1,x,y);ans+=run(x)+run(y);}
    // for(int i=1;i<=cnt;i++) printf("%d : c=%d ls=%d rs=%d fa=%d L=%d R=%d\n",i,c[i],ls[i],rs[i],fa[i],L[i],R[i]);
    if(check(v)){ int pv=get(v-1),x,y;ans-=run(pv);split(pv,1,n-1,u,v-1,x,y);ans+=run(x)+run(y);}
    // for(int i=1;i<=cnt;i++) printf("%d : c=%d ls=%d rs=%d fa=%d L=%d R=%d\n",i,c[i],ls[i],rs[i],fa[i],L[i],R[i]);
}
int build(int pl,int pr)
{
    if(pl==pr)
    {
        L[pl]=R[pl]=pl;c[pl]=1;
        return pl;
    }
    int p=++cnt,mid=(pl+pr)>>1;fa[p]=0;
    ls[p]=build(pl,mid);
    rs[p]=build(mid+1,pr);
    push_up(p);
    return p;
}
inline void solve()
{
    clear();
    n=read(),m=read(),cnt=n-1;
    for(int i=1;i<n;i++) S0.insert(i);
    ans=run(build(1,n-1));
    for(int i=1;i<=m;i++)
    {
        edge();
        ll o=ans+(int)S1.size()+(ll)S0.size()*(n-1-S0.size()+i);
        // printf("ans=%lld %lld %lld\n",ans,(ll)S0.size(),n-1-(ll)S0.size()+i);
        printf("%lld\n",o);
    }
}
int main()
{
    int T=read();L[0]=0x3f3f3f3f,R[0]=0;
    while(T--) solve();
    return 0;
}
/*
1
4 2
2 4
2 4
*/