#include <stdio.h>
#include <string.h>
#define N 30
#define Max 5000000
int mal[N][N], fem[N][N], fem_chose[N], mal_alone[N], n,Q[Max];
int hash[256];
char mrel[256], wrel[256], str[100];
void gale_shapley()
{
	int head=0, tail=0, i, boy, girl, pre;
	memset(fem_chose,-1,sizeof(fem_chose));
	memset(mal_alone,0,sizeof(mal_alone));
	for(i=1;i<=n;i++)
		Q[++tail]=i;
	while(head!=tail)
	{
		boy=Q[++head];
		for(i=1;i<=n;i++)
		{
			girl=mal[boy][i];
			if(fem[girl][boy]!=-1)
			{
				pre=fem_chose[girl];
				if(pre==-1)          //该女未订婚
				{
					fem_chose[girl]=boy;
					mal_alone[boy]=girl;
					break;
				}
				else if(fem[girl][boy]<fem[girl][pre])  ////该女为之悔婚
				{

					Q[++tail]=pre;
					fem_chose[girl]=boy;
					mal_alone[boy]=girl;
					fem[girl][pre]=-1;
					break;
				}
				else  fem[girl][boy]=-1;     ///该女拒绝之
			}
		}
	}
}
int main()
{
	int icase, i, j;
	char ch;
	scanf("%d",&icase);
	while(icase--)
	{
		scanf("%d%*c",&n);
		memset(hash,0,sizeof(hash));
		for(i=1;i<=n;i++)
		{
			ch=getchar();
			getchar();
			hash[ch]=i;
			mrel[i]=ch;
		}
		for(i=1;i<=n;i++)
		{
			ch=getchar();
			hash[ch]=i;
			wrel[i]=ch;
		}
		for(i=1;i<=n;i++)
		{
			scanf("%c:%s%*c",&ch,str);
			for(j=1;j<=n;j++)
				mal[hash[ch]][j]=hash[str[j-1]];
		}
		for(i=1;i<=n;i++)
		{
			getchar();
			scanf("%c:%s%*c",&ch,str);
			for(j=1;j<=n;j++)
				fem[hash[ch]][j]=hash[str[j-1]];
		}
		gale_shapley();
		for(i='a';i<='z';i++)
		{
			if(hash[i])
			{
				printf("%c %c\n",i,wrel[mal_alone[hash[i]]]);
			}
		}
		printf("\n");
	}
	return 0;
}