#include<bits/stdc++.h>
using namespace std;
#define xx first
#define yy second
#define pb push_back

typedef long long ll;

const int MAXN=200001;
struct el {
	int x;
	int id;
};

vector<el> adj[MAXN];
vector<int> cadj[MAXN];

//Explore different components

int compid=1;
int comp[MAXN], compsz[MAXN];

int b1[MAXN];
void dfs1(int x, int cid) {
	b1[x]=1;
	comp[x]=cid;
	compsz[cid]++;
	for(auto ii:adj[x]) {
		int i=ii.x;
		if(b1[i]) continue ;
		dfs1(i, cid);
	}

	b1[x]=2;
}


//Explore different cycles

int cycid=1;
int cycle[MAXN], par2[MAXN], b2[MAXN];
void dfs2(int x) {
	b2[x]=1;
	for(auto ii:adj[x]) {
		int i=ii.x;
		if(b2[i]==1 && par2[x]!=i) {
			int akt=x;
			while(1) {
				cycle[akt]=cycid;
				if(akt==i) {
					break ;
				}

				akt=par2[akt];
			}

			cycid++;
		}else if(b2[i]==0) {
			par2[i]=x;
			dfs2(i);
		}
	}
	b2[x]=2;
}

//Explore different "components" between cycles

int simaszptr=0;
int simaszcont[MAXN];
int* simasz[MAXN];

int b3[MAXN];

void dfs3(int x) {
	b3[x]=1;
	simasz[x]=&simaszcont[simaszptr];
	simaszcont[simaszptr]++;

	for(auto ii:adj[x]) {
		int i=ii.x;
		if(b3[i]) {
			continue;
		}

		if(cycle[i]==0 || cycle[x]==0 || cycle[i]!=cycle[x]) {
			dfs3(i);
		}
	}

	b3[x]=2;
}


int fullszptr=0;
int fullszcont[MAXN];
int* fullsz[MAXN];

int b35[MAXN];

void dfs35(int x) {
    b35[x]=1;
    fullsz[x]=&fullszcont[fullszptr];
    fullszcont[fullszptr]++;

    for(auto i:cadj[x]) {
        fullszcont[fullszptr]+=*simasz[i];
    }

    for(auto ii:adj[x]) {
        int i=ii.x;
        if(b35[i]) {
            continue ;
        }

        if(cycle[i]==0 || cycle[x]==0 || cycle[i]!=cycle[x]) {
			dfs35(i);
		}
    }

    b35[x]=2;
}

//Solve the problem inside the "components" between cycles

int b4[MAXN];

//<sima, full>
pair<int,int> dfs4(int x, vector<ll>& ans) {
	b4[x]=1;
	int subsimasz=1, subfullsz=1;
	for(auto i:cadj[x]) {
        subfullsz+=*simasz[i];
	}

	for(auto ii:adj[x]) {
		int i=ii.x;
		if(b4[i]) {
			continue ;
		}

		if(cycle[i]==0 || cycle[i]!=cycle[x]) {
			pair<int,int> akt=dfs4(i, ans);
			subsimasz+=akt.xx;
			subfullsz+=akt.yy;

			ans[ii.id]=ll(akt.yy)*ll(*simasz[x]-akt.xx)+ll(*fullsz[x]-akt.yy)*ll(akt.xx)-ll(akt.xx)*ll(*simasz[x]-akt.xx);
		}

	}
	b4[x]=2;

	return make_pair(subsimasz, subfullsz);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
	int T;
	cin>>T;
	while(T--) {
		int n,m;
		cin>>n>>m;

		vector<pair<int,int>> lst(m);

		compid=1;
		simaszptr=0;
		fullszptr=0;
		cycid=1;
		//@TODO init everything
		for(int i=0;i<=n;++i) {
			adj[i].clear();
			cadj[i].clear();

			comp[i]=0;
			compsz[i]=0;
			b1[i]=b2[i]=b3[i]=b35[i]=b4[i]=0;

			simaszcont[i]=0;
			simasz[i]=nullptr;

			fullszcont[i]=0;
			fullsz[i]=nullptr;


			cycle[i]=0;

			par2[i]=-1;
		}

		for(int i=0;i<m;++i) {
			cin>>lst[i].xx>>lst[i].yy;
			adj[lst[i].xx].pb({lst[i].yy, i});
			adj[lst[i].yy].pb({lst[i].xx, i});
		}

		for(int i=1;i<=n;++i) {
			if(!b1[i]) {
				dfs1(i, compid++);
			}
		}

		for(int i=1;i<=n;++i) {
			if(!b2[i]) {
				dfs2(i);
			}
		}

        for(int i=1;i<=n;++i) {
            if(cycle[i]){
                for(auto j:adj[i]) {
                    if(cycle[j.x]==cycle[i]) {
                        cadj[i].pb(j.x);
                    }
                }
            }
        }

		for(int i=1;i<=n;++i) {
			if(!b3[i]) {
				dfs3(i);simaszptr++;
			}
		}

        for(int i=1;i<=n;++i) {
			if(!b35[i]) {
				dfs35(i);fullszptr++;
			}
		}

		vector<ll> ans(m, -1);
		for(int i=1;i<=n;++i) {
			if(!b4[i]) {
				dfs4(i, ans);
			}
		}

		for(int i=0;i<m;++i){
			if(ans[i]==-1) {
				ans[i]=(ll(*simasz[lst[i].xx])*ll(*simasz[lst[i].yy]));
			}
		}

		for(int i=0;i<m;++i) {
			cout<<ans[i]<<"\n";
		}

	}

	return 0;
}