#include <bits/stdc++.h>
using namespace std;
int T;
int n,m,q;
const int maxn=500005; 
vector<int>a[maxn];
int dfn[maxn],low[maxn],tim;
int f[maxn][33];
bool v[maxn];
int siz[maxn];
int tot[maxn];
int dep[maxn];
void tarjan(int x){
	dfn[x]=low[x]=++tim;
	siz[x]=1;
	tot[x]=0;
	int cnt=0;
	for(int y:a[x]){
		if(!dfn[y]){
			f[y][0]=x;
			//cout<<"there build a road: "<<x<<" "<<y<<endl;
			dep[y]=dep[x]+1;
			tarjan(y);
			siz[x]+=siz[y];
			low[x]=min(low[x],low[y]);
			if(low[y]>=dfn[x]){
				cnt++;
				tot[x]+=siz[y];
			}
		}
		else{
			low[x]=min(low[x],dfn[y]);
		}
	}
	if(f[x][0]==0&&cnt>=2)
		v[x]=true;
	if(f[x][0]!=0&&cnt>=1)
		v[x]=true;
}
int lca(int x,int y){
	if(dep[x]<dep[y])
		swap(x,y);
	for(int stp=30;stp>=0;stp--){
		int xx=f[x][stp];
		if(dep[xx]>=dep[y]){
			x=xx;
		}
	}
	if(x==y)
		return x;
	for(int stp=30;stp>=0;stp--){
		int xx=f[x][stp],yy=f[y][stp];
		if(xx==yy)
			continue;
		else
			x=xx,y=yy;
	}
	x=f[x][0],y=f[y][0];
	return x;
}
int getnum(int x,int y){
	if(f[x][0]==0){
		for(int yy:a[x]){
			if(yy==f[x][0])
				continue;
			if(lca(y,yy)==x)
				continue;
			return n-siz[yy]-1;
		}
	}
	int fa=lca(x,y);
	if(fa==y){
		return tot[x];
	}
	else if(fa==x){
		for(int yy:a[x]){
			if(yy==f[x][0])
				continue;
			if(lca(y,yy)==x)
				continue;
			if(low[yy]<dfn[x])
				return 0;
			else
				return n-siz[yy]-1;
		}
	}
	else{
		return tot[x];
	}
}
int main(){
	cin>>T;
	while(T--){
		memset(v,0,sizeof(v));
		memset(f,0,sizeof(f));
		memset(dfn,0,sizeof(dfn));
		memset(low,0,sizeof(low));
		memset(siz,0,sizeof(siz));
		tim=0;
		cin>>n>>m;
		for(int i=1;i<=n;i++)
			a[i].clear();
		for(int i=1;i<=m;i++){
			int x,y;cin>>x>>y;
			a[x].push_back(y);
			a[y].push_back(x);
		}
		for(int i=1;i<=n;i++){
			if(!dfn[i]){
				dep[i]=1;
				tarjan(i);
			}
		}
		for(int stp=1;stp<=30;stp++){
			for(int i=1;i<=n;i++){
				f[i][stp]=f[f[i][stp-1]][stp-1];
			}
		}
		cin>>q;
		for(int i=1;i<=q;i++){
			int x,y;cin>>x>>y;
			int ans=n;
			if(v[x])
				ans-=getnum(x,y);
			if(v[y])
				ans-=getnum(y,x);
			cout<<ans<<endl;
		}
	}
	return 0;
}
/*
1
5 5
1 2
1 3
2 4
4 5
2 5
1
2 5
*/