#include<cstdio>

#include<cstring>

#include<algorithm>

#define MN 5100000

using namespace std;

struct na{int x,y,ne;}b[MN<<];

int n,m,t,x,y,st[MN],c[MN],s[MN],S[MN],num,l[MN],pdf[MN],nm;

long long ans[MN];

bool bo[MN],W[MN<<];

inline void add(int x,int y){b[++num].x=x;b[num].y=y;b[num].ne=l[x];l[x]=num;W[num]=;}

void pre(int x,int f){

    bo[x]=;pdf[++nm]=x;//printf("%d %d\n",nm,x);

    for (int i=l[x];i;i=b[i].ne)

    if (b[i].y!=f)

    if (bo[b[i].y]) pre(b[i].y,x);

}

void dfs(int x,int p,int f){

    bo[x]=;

    for (int i=l[x];i;i=b[i].ne)

    if (!W[i]&&b[i].y!=f)

    if (!bo[b[i].y]) st[p]=i,dfs(b[i].y,p+,x);else{

        W[i]=W[i^]=;

        for (int j=p-;j>=;j--){

            W[st[j]]=W[st[j]^]=;

            if (b[st[j]].x==b[i].y) break;

        }

    }

}

void DFS(int x,int f){

    bo[x]=;s[x]=;

    //printf("%d %d\n",x,s[x]);

    for (int i=l[x];i;i=b[i].ne)

    if (b[i].y!=f&&!W[i]) DFS(b[i].y,x),s[x]+=s[b[i].y];

}

void _DFS(int x,int f,int w){

    bo[x]=;

    for (int i=l[x];i;i=b[i].ne)

    if (b[i].y!=f&&!W[i]) _DFS(b[i].y,x,w+s[x]-s[b[i].y]);

    S[x]=s[x]+w;

}

void work(int x,int f){

    bo[x]=;

    for (int i=l[x];i;i=b[i].ne)

    if (b[i].y!=f)

    if (!W[i]) work(b[i].y,x),c[x]+=c[b[i].y];else{

        if (bo[b[i].y]) work(b[i].y,x);

        c[x]+=S[b[i].y];

    }

}

void _work(int x,int f,int w1,int w2){

    bo[x]=;

    for (int i=l[x];i;i=b[i].ne)

    if (b[i].y!=f)

    if (W[i]){

        if (!bo[b[i].y]) _work(b[i].y,x,,S[x]);

        ans[i>>]=1LL*S[x]*S[b[i].y];

    }else{

        _work(b[i].y,x,w1+s[x]-s[b[i].y],w2+c[x]-c[b[i].y]);

        ans[i>>]=1LL*(S[x]-s[b[i].y])*s[b[i].y]+1LL*s[b[i].y]*(w2+c[x]-c[b[i].y])+1LL*(S[x]-s[b[i].y])*c[b[i].y];

    }

}

int main(){

    scanf("%d",&t);

    while(t--){

        scanf("%d%d",&n,&m);

        memset(st,,(n+)*);

        memset(c,,(n+)*);

        memset(s,,(n+)*);

        memset(S,,(n+)*);

        memset(pdf,,(n+)*);

        num=;nm=;

        for (int i=;i<=n;i++) l[i]=,bo[i]=;

        for (int i=;i<=m;i++) scanf("%d%d",&x,&y),add(x,y),add(y,x),ans[i]=;

        for (int i=;i<=n;i++)

        if (bo[i])

        pre(i,);

        for (int i=;i<=n;i++)

        if (!bo[pdf[i]])

        dfs(pdf[i],,);

        for (int i=;i<=n;i++)

        if (bo[pdf[i]]) DFS(pdf[i],);

        for (int i=;i<=n;i++)

        if (!bo[pdf[i]]) _DFS(pdf[i],,);

        for (int i=;i<=n;i++)

        if (bo[pdf[i]]) work(pdf[i],);

        for (int i=;i<=n;i++)

        if (!bo[pdf[i]]) _work(pdf[i],,,);

        for (int i=;i<=m;i++) printf("%lld\n",ans[i]);

        //printf("%d %d %d %d\n",S[1],S[2],S[3],S[4]);

        //printf("%d %d %d %d %d %d\n",W[2],W[3],W[4],W[5],W[6],W[7]);

    }

}