#include <bits/stdc++.h>
using namespace std;
map<string,vector<string> >graph;
queue<string>Q;
map<string,int>visit;
map<string,string>lis;
void BFS(string s,string e)
{
Q.push(s);
visit[s]++;
while(!Q.empty())
{
string f=Q.front();
Q.pop();
for(int i=0; i<graph[f].size(); ++i)
{
string temp=graph[f][i];
if(visit[temp]==0)
{
Q.push(temp);
visit[temp]++;
lis[temp]=f;
if(temp==e) break;
}
}
}
}
void printlist(string e,string s)
{
if(e==s)
{
cout<<e[0];
return;
}
printlist(lis[e],s);
cout<<e[0];
}
int main()
{
int test;
cin>>test;
bool flag=true;
while(test--)
{
int m,n;
if(!flag)printf("\n");
cin>>m>>n;
flag=false;
graph.clear();
while(m--)
{
string a,b;
cin>>a>>b;
graph[a].push_back(b);
graph[b].push_back(a);
}
while(n--)
{
string s ,e;
cin>>s>>e;
lis.clear();
visit.clear();
BFS(s,e);
printlist(e,s);
cout<<endl;
}
}
return 0;
}
using namespace std;
map<string,vector<string> >graph;
queue<string>Q;
map<string,int>visit;
map<string,string>lis;
void BFS(string s,string e)
{
Q.push(s);
visit[s]++;
while(!Q.empty())
{
string f=Q.front();
Q.pop();
for(int i=0; i<graph[f].size(); ++i)
{
string temp=graph[f][i];
if(visit[temp]==0)
{
Q.push(temp);
visit[temp]++;
lis[temp]=f;
if(temp==e) break;
}
}
}
}
void printlist(string e,string s)
{
if(e==s)
{
cout<<e[0];
return;
}
printlist(lis[e],s);
cout<<e[0];
}
int main()
{
int test;
cin>>test;
bool flag=true;
while(test--)
{
int m,n;
if(!flag)printf("\n");
cin>>m>>n;
flag=false;
graph.clear();
while(m--)
{
string a,b;
cin>>a>>b;
graph[a].push_back(b);
graph[b].push_back(a);
}
while(n--)
{
string s ,e;
cin>>s>>e;
lis.clear();
visit.clear();
BFS(s,e);
printlist(e,s);
cout<<endl;
}
}
return 0;
}