#include<cstdio>
#include<string>
#include<queue>
#include<vector>
#include<iostream>
#include<map>
using namespace std;
int main()
{
int i,j,k,m,n,t,tcase=1,p;
string a,b;
scanf("%d",&t);
while(t--){
printf("\n");
vector<int>list[2000];
map<char,int>maps1;
map<int,char>maps2;
scanf("%d %d",&m,&n);
for(i=1,j=1;i<=m;i++){
cin>>a>>b;
if(maps1[a[0]]==0) maps1[a[0]]=j,maps2[j]=a[0],j++;
if(maps1[b[0]]==0) maps1[b[0]]=j,maps2[j]=b[0],j++;
list[maps1[a[0]]].push_back(maps1[b[0]]);
list[maps1[b[0]]].push_back(maps1[a[0]]);
}
for(p=1;p<=n;p++){
int flag=0;
cin>>a>>b;
vector<int>taken(2000);
vector<string>level(2000);
queue<int>q;
q.push(maps1[a[0]]);
taken[maps1[a[0]]]=1;
level[maps1[a[0]]]=a[0];
while(!q.empty()){
k=q.front();
for(i=0;i<list[k].size();i++){
if(taken[list[k][i]]==0){
taken[list[k][i]]=1;
level[list[k][i]]=level[k]+maps2[list[k][i]];
q.push(list[k][i]);
if(maps2[list[k][i]]==b[0]){
cout<<level[list[k][i]]<<"\n";
flag=1;
break;
}
}
}
if(flag==1) break;
q.pop();
}
}
}
return 0;
}
I2luY2x1ZGU8Y3N0ZGlvPgojaW5jbHVkZTxzdHJpbmc+CiNpbmNsdWRlPHF1ZXVlPgojaW5jbHVkZTx2ZWN0b3I+CiNpbmNsdWRlPGlvc3RyZWFtPgojaW5jbHVkZTxtYXA+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgppbnQgbWFpbigpCnsKICAgIGludCBpLGosayxtLG4sdCx0Y2FzZT0xLHA7CiAgICBzdHJpbmcgYSxiOwogICAgc2NhbmYoIiVkIiwmdCk7CiAgICB3aGlsZSh0LS0pewogICAgICAgIHByaW50ZigiXG4iKTsKICAgICAgICB2ZWN0b3I8aW50Pmxpc3RbMjAwMF07CiAgICAgICAgbWFwPGNoYXIsaW50Pm1hcHMxOwogICAgICAgIG1hcDxpbnQsY2hhcj5tYXBzMjsKICAgICAgICBzY2FuZigiJWQgJWQiLCZtLCZuKTsKICAgICAgICBmb3IoaT0xLGo9MTtpPD1tO2krKyl7CiAgICAgICAgICAgIGNpbj4+YT4+YjsKICAgICAgICAgICAgaWYobWFwczFbYVswXV09PTApIG1hcHMxW2FbMF1dPWosbWFwczJbal09YVswXSxqKys7CiAgICAgICAgICAgIGlmKG1hcHMxW2JbMF1dPT0wKSBtYXBzMVtiWzBdXT1qLG1hcHMyW2pdPWJbMF0saisrOwogICAgICAgICAgICBsaXN0W21hcHMxW2FbMF1dXS5wdXNoX2JhY2sobWFwczFbYlswXV0pOwogICAgICAgICAgICBsaXN0W21hcHMxW2JbMF1dXS5wdXNoX2JhY2sobWFwczFbYVswXV0pOwogICAgICAgIH0KICAgICAgICBmb3IocD0xO3A8PW47cCsrKXsKICAgICAgICAgICAgaW50IGZsYWc9MDsKICAgICAgICAgICAgY2luPj5hPj5iOwogICAgICAgICAgICB2ZWN0b3I8aW50PnRha2VuKDIwMDApOwogICAgICAgICAgICB2ZWN0b3I8c3RyaW5nPmxldmVsKDIwMDApOwogICAgICAgICAgICBxdWV1ZTxpbnQ+cTsKICAgICAgICAgICAgcS5wdXNoKG1hcHMxW2FbMF1dKTsKICAgICAgICAgICAgdGFrZW5bbWFwczFbYVswXV1dPTE7CiAgICAgICAgICAgIGxldmVsW21hcHMxW2FbMF1dXT1hWzBdOwogICAgICAgICAgICB3aGlsZSghcS5lbXB0eSgpKXsKICAgICAgICAgICAgICAgIGs9cS5mcm9udCgpOwogICAgICAgICAgICAgICAgZm9yKGk9MDtpPGxpc3Rba10uc2l6ZSgpO2krKyl7CiAgICAgICAgICAgICAgICAgICAgaWYodGFrZW5bbGlzdFtrXVtpXV09PTApewogICAgICAgICAgICAgICAgICAgICAgICB0YWtlbltsaXN0W2tdW2ldXT0xOwogICAgICAgICAgICAgICAgICAgICAgICBsZXZlbFtsaXN0W2tdW2ldXT1sZXZlbFtrXSttYXBzMltsaXN0W2tdW2ldXTsKICAgICAgICAgICAgICAgICAgICAgICAgcS5wdXNoKGxpc3Rba11baV0pOwogICAgICAgICAgICAgICAgICAgICAgICBpZihtYXBzMltsaXN0W2tdW2ldXT09YlswXSl7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICBjb3V0PDxsZXZlbFtsaXN0W2tdW2ldXTw8IlxuIjsKICAgICAgICAgICAgICAgICAgICAgICAgICAgIGZsYWc9MTsKICAgICAgICAgICAgICAgICAgICAgICAgICAgIGJyZWFrOwogICAgICAgICAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgaWYoZmxhZz09MSkgYnJlYWs7CiAgICAgICAgICAgICAgICBxLnBvcCgpOwogICAgICAgICAgICB9CiAgICAgICAgfQogICAgfQogICAgcmV0dXJuIDA7Cn0K