#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
inline int read()
{
	char c=getchar();int x=0;bool f=0;
	for(;!isdigit(c);c=getchar())f^=!(c^45);
	for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
	if(f)x=-x;return x;
}

#define fi first
#define se second
#define pb push_back
#define mkp make_pair
typedef pair<int,int>pii;
typedef vector<int>vi;

#define maxn 1000005
#define inf 0x3f3f3f3f

int n,m,cnt;

vi e[maxn],g[maxn];
int dfn[maxn],low[maxn],bel[maxn],idx,fa[maxn][20];
int stk[maxn],tp;
void tar(int u,int pa)
{
	dfn[u]=low[u]=++idx,stk[++tp]=u;
	for(auto v:e[u]){
		if(v==pa)continue;
		if(!dfn[v]){
			tar(v,u);
			low[u]=min(low[u],low[v]);
			if(low[v]>=dfn[u]){
				++cnt; int x; 
				g[u].pb(cnt); fa[cnt][0]=u;
				do{
					x=stk[tp--];
					g[cnt].pb(x),bel[x]=cnt; //cout<<"addg "<<cnt<<" "<<x<<endl;
					fa[x][0]=cnt;
				}while(x!=v);
			}
		}
		else low[u]=min(low[u],dfn[v]);
	}
}

int sz[maxn],dep[maxn];
int L[maxn],R[maxn],qwq;
void dfs(int u,int pa){
	sz[u]=(u<=n);
	L[u]=++qwq; dep[u]=dep[pa]+1;
	For(i,1,19) fa[u][i]=fa[fa[u][i-1]][i-1];
	for(int v:g[u])if(v!=pa)dfs(v,u),sz[u]+=sz[v];
	R[u]=qwq;
}

int kth(int u,int k){
	For(i,0,19)if(k>>i&1)u=fa[u][i];
	return u;
}
int jump(int u,int v){return kth(u,dep[u]-dep[v]-1);}

void work()
{
	n=read(),m=read(),cnt=n;idx=0;
	For(i,1,n*2){
		e[i].clear(),g[i].clear();
		dfn[i]=low[i]=bel[i]=sz[i]=0;
	}
	For(i,1,m){
		int u=read(),v=read();
		e[u].pb(v),e[v].pb(u);
	}
	tar(1,0);
	qwq=0;
	dfs(1,0);
	int q=read();
	while(q--){
		int res=0,u=read(),v=read();
		if(L[u]>L[v])swap(u,v);
		if(L[u]<=L[v] && R[u]>=R[v]){
			int w=jump(v,u);
			res=sz[w]-sz[v]+2;
		}else{
			res=n-sz[u]-sz[v]+2;
		}
		printf("%d\n",res);
	}
}

signed main()
{
	int T=read();
	while(T--)work();
	return 0;
}