因为两棵树中间只有k条边，所以这些边一定要用到。
对于每棵树分别考虑：
如果一个点往下连着两个点，那么这个点往上的那条边一定不能用到。
如果一个点往下连着一个点，那么这个点往上的那条边一定不能用到。
否则一定无解。
这样求出所有一定要用到的边后，如果不存在奇点且这个图是个连通图的话，那么就有解。时间复杂度$O(n+m+k)$。
#include<cstdio>
#include<cstring>
#define N 10010
int T,k,n,m,i,d[N],vis[N],g[N],v[N],ok[N],nxt[N],ed,flag;char sa[N],sb[N];
int getid(char s[]){
int l=std::strlen(s),x=0;
for(int i=2;i<l;i++)x=x*10+s[i]-'0';
if(s[0]=='A'){
if(s[1]=='S')return x;
return x+k;
}
if(s[1]=='S')return x+k+n;
return x+k*2+n;
}
void printname(int x){
if(x<=k){printf("AS%d",x);return;}
if(x<=k+n){printf("AP%d",x-k);return;}
if(x<=k*2+n){printf("BS%d",x-k-n);return;}
printf("BP%d",x-k*2-n);
}
void add(int x,int y){
v[++ed]=y;ok[ed]=1;nxt[ed]=g[x];g[x]=ed;d[x]++;
v[++ed]=x;ok[ed]=1;nxt[ed]=g[y];g[y]=ed;d[y]++;
}
int dfs1(int x,int y,int w){
if(x<=k)return 1;
if(x>k+n)return 0;
int t=0;
for(int i=g[x];i;i=nxt[i])if(v[i]!=y)t+=dfs1(v[i],x,i);
if(!t||t>2)return flag=1,0;
if(t==1)return 1;
if(w)d[x]--,d[y]--,ok[w]=ok[w^1]=0;
return 0;
}
int dfs2(int x,int y,int w){
if(x>k+n&&x<=k*2+n)return 1;
if(x<=k+n)return 0;
int t=0;
for(int i=g[x];i;i=nxt[i])if(v[i]!=y)t+=dfs2(v[i],x,i);
if(!t||t>2)return flag=1,0;
if(t==1)return 1;
if(w)d[x]--,d[y]--,ok[w]=ok[w^1]=0;
return 0;
}
void dfs3(int x){
if(vis[x])return;
vis[x]=1;
for(int i=g[x];i;i=nxt[i])if(ok[i])dfs3(v[i]);
}
void dfs4(int x){
if(vis[x])return;
vis[x]=1;
putchar(' ');printname(x);
for(int i=g[x];i;i=nxt[i])if(ok[i])dfs4(v[i]);
}
int main(){
scanf("%d",&T);
while(T--){
scanf("%d%d%d",&k,&n,&m);
for(ed=i=1;i<=n+m+k*2;i++)g[i]=d[i]=vis[i]=0;flag=0;
for(i=1;i<=n+m+k*3-2;i++)scanf("%s%s",sa,sb),add(getid(sa),getid(sb));
dfs1(k+1,0,0),dfs2(k*2+n+1,0,0);
for(i=1;i<=n+m+k*2;i++)if(d[i]&1)flag=1;
dfs3(1);
for(i=1;i<=n+m+k*2;i++)if(!vis[i])flag=1;
if(flag)puts("NO");
else{
printf("YES");
for(i=1;i<=n+m+k*2;i++)vis[i]=0;
dfs4(1);
puts("");
}
}
return 0;
}