#include<cstdio>

 #include<iostream>

 #include<map>

 #include<string>

 #define F(i,a,b) for(int i=a;i<=b;i++)

 #pragma comment(linker, "/STACK:1024000000,1024000000")

 using namespace std;

 map<string,int>cnt;

 const int N=1e5+,DEG=;

 int t,n,m,a,b,ed,g[N],nxt[N],v[N],w[N],fa[N][DEG],dep[N],idx;

 bool fg[N];

 string s1,s2;

 inline void adg(int x,int y){v[++ed]=y,nxt[ed]=g[x],g[x]=ed;}

 int Abs(int a){return a>?a:-a;}

 void dfs(int u,int pre){

     dep[u]=dep[pre]+,fa[u][]=pre;

     F(i,,DEG-)fa[u][i]=fa[fa[u][i-]][i-];

     for(int i=g[u];~i;i=nxt[i])if(v[i]!=pre)dfs(v[i],u);

 }

 int LCA(int a,int b){

     if(dep[a]>dep[b])a^=b,b^=a,a^=b;

     if(dep[a]<dep[b])F(i,,DEG-)if((dep[b]-dep[a])&(<<i))b=fa[b][i];

     if(a!=b)for(int i=DEG-;i<?a=fa[a][]:,i>=;i--)

     if(fa[a][i]!=fa[b][i])a=fa[a][i],b=fa[b][i];

     return a;

 }

 int main(){

     scanf("%d",&t);

     while(t--){

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

         cnt.clear();

         F(i,,n)g[i]=-,fg[i]=;ed=,idx=;

         F(i,,n-){

             cin>>s1>>s2;

             a=cnt[s1],cnt[s1]=(a==)?idx++:a,a=(a==?idx-:a);

             b=cnt[s2],cnt[s2]=(b==)?idx++:b,b=(b==?idx-:b);

             adg(b,a),fg[a]=;

         }

         int root;

         F(i,,n)if(!fg[i]){root=i;break;}

         dep[root]=;

         dfs(root,root);

         F(i,,m){

             cin>>s1>>s2;

             a=cnt[s1],b=cnt[s2];

             int lca=LCA(a,b),ans=;

             if(lca==a&&lca!=b)ans=;

             else if(lca==b&&lca!=a)ans=Abs(dep[a]-dep[b]);

             else if(lca!=a&&lca!=b)ans=Abs(dep[a]-dep[lca])+;

             printf("%d\n",ans);

         }

     }

     return ;

 }