#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
ll n,m,i,j,k,l,r,x,y,z,w,s,t,a[1100000],b[1100000],depth[1100000],h[1100000],siz[1100000],chk[1100000],par[1100000],sparse[20][220000],q,maximum[1100000],e,ee;
vector<ll> v[1100000],u[1100000];
void construct_dfstree(ll x)
{
    chk[x]=1;
    maximum[x]=depth[x];
    ll i;
    for(i=0;i<u[x].size();i++)
    {
        if(chk[u[x][i]]&&depth[x]>depth[u[x][i]])
        {
            //addedge[x].push_back(u[x][i]);
            maximum[x]=min(maximum[x],depth[u[x][i]]);
        }
        if(chk[u[x][i]]&&depth[x]<depth[u[x][i]])
        {
            //deledge[x]++;
        }
        if(chk[u[x][i]])
            continue;
        depth[u[x][i]]=depth[x]+1;
        v[x].push_back(u[x][i]);
        par[u[x][i]]=x;
        construct_dfstree(u[x][i]);
    }
}
void dfs(ll x,ll y)
{
    ll i;
    siz[x]=1;
    //swap(backedge[x],addedge[x]);
    for(i=0;i<v[x].size();i++)
    {
        dfs(v[x][i],x);
        maximum[x]=min(maximum[x],maximum[v[x][i]]);
        siz[x]+=siz[v[x][i]];
        if(maximum[v[x][i]]<depth[x])
            b[x]+=siz[v[x][i]];
    }
}
ll desc(ll x,ll y)
{
    ll i;
    for(i=19;i>=0;i--)
    {
        if(depth[x]-(1<<i)>depth[y])
            x=sparse[i][x];
    }
    return x;
}
ll is_par(ll x,ll y)
{
    if(depth[x]<depth[y])
        return 0;
    ll i;
    for(i=19;i>=0;i--)
    {
        if(depth[x]-(1<<i)>=depth[y])
           {
               x=sparse[i][x];
           }
    }
    if(x==y)
        return 1;
    return 0;
}
int main()
{
    scanf("%lld",&e);
    for(ee=0;ee<e;ee++)
    {
        scanf("%lld %lld",&n,&m);
        for(i=1;i<=n;i++)
        {
            v[i].clear();
            u[i].clear();
            b[i]=0;
            a[i]=0;
        }
        for(i=1;i<=m;i++)
        {
            scanf("%lld %lld",&x,&y);
            u[x].push_back(y);
            u[y].push_back(x);
        }
        for(i=1;i<=n;i++)
        {
            depth[i]=0;
            chk[i]=0;
            par[i]=0;
            siz[i]=0;
        }
        depth[1]=1;
        construct_dfstree(1);
        dfs(1,0);
        for(i=1;i<=n;i++)
        {
            sparse[0][i]=par[i];
         //   printf("(%lld:%lld)\n",i,par[i]);
        }
        for(j=1;j<=19;j++)
        {
            for(i=1;i<=n;i++)
            {
                sparse[j][i]=sparse[j-1][sparse[j-1][i]];
            }
        }
        scanf("%lld",&q);
        for(i=1;i<=q;i++)
        {
            scanf("%lld %lld",&x,&y);
            if(depth[x]<depth[y])
                swap(x,y);
            if(!is_par(x,y))
            {
                printf("%lld\n",n-siz[x]-siz[y]+2+b[x]+b[y]);
                continue;
            }
            //printf("(!)");
            s=0;
            s+=b[x];
            //printf("[%lld]\n",b[x]);
            s++;
            //s+=siz[y]-siz[x];
            s+=siz[desc(x,y)]-siz[x];
            s++;
            //printf("(%lld)\n",desc(x,y));
            if(maximum[desc(x,y)]<depth[y])
                s+=n-siz[y]+b[y]-siz[desc(x,y)];
            printf("%lld\n",s);
        }
    }
}