[Cerc2012]Graphic Madness

时间限制:10s      空间限制:128MB

题目描述

 在Byteland有两家领导显卡行业的制作商:Bitotronics和3D-Bytes。他们顶级的显卡十分相像。每一个都包含一些电线连接节点,用来维护电信号传播。产品包括两种节点:插座和处理器。这种有线网络满足以下条件:

每个插座都恰好和一个处理器相连,不和任何其他插座相连。
每个处理器都和至少两个其他的节点相连。
任意两个在网络中的节点,都只存在唯一的电线路径链接他们。换句话说,这些节点之间的连通图可以被看成是一棵树。
Bitthew喜欢焊接计算机的硬件设备。他拿出了来自两个不同厂家的显卡,两个显卡拥有相同数量的插座,他决定将每个Bitotronics卡上的插座与3D-Bytes卡上的插座用电缆一一相连。他得到的装置如图:
 
Bitthew想要从装置中获得出最大的性能。为了实现这个目标,他想要找到一条由电线和电缆组成的路径来维护电信号。这条路径应该访问每个节点恰好一次,且这条路径的起始节点和终止节点应该在同一个节点。请你帮助Bitthew检查一下现在的装置是否能找到这样的路径。


输入格式

第一行一个正整数T,表示有T组数据。

每组数据第一行三个整数k, n, m,表示每个卡有k个插座,Bitotronics卡有n个处理器,3D-Bytes卡有m个处理器,2 <= k <= 1000, 1 <= n, m <= 1000。卡上的节点按照以下形式命名:
Bitotronics卡的插座:AS1, AS2, ..., Ask
Bitotronics卡的处理器:AP1, AP2, ..., APn
3D-Bytes卡的插座:BS1, BS2, ..., BSk
3D-Bytes卡的处理器:BP1, BP2, ..., BPm
接下来n+k-1行描述Bitotronics卡的情况,每行两个节点的名字,表示这两个节点之间有电线相连。接下来一行为空行。
接下来m+k-1行描述3D-Bytes卡的情况,每行两个节点的名字,表示这两个节点之间有电线相连。接下来一行为空行。
接下来k行描述两卡之间的情况,每行两个节点的名字,表示这两个节点之间有电缆相连,保证每个插座在这k行里均只出现一次。
每组数据之间会有一个空行。


输出格式

对于每组数据,如果不存在这样的路径,输出一行"NO",否则先输出一行"YES",再在其后按照路径上的顺序输出n+m+2k个节点,相邻的节点必须通过电线或电缆直接相连,而且第一个点必须和最后一个点也直接相连,按照任意顺序输出,节点名称和”YES”之间空格隔开。(不含引号)


样例输入

1
2 1 11
AS1 AP1
AS2 AP1
BS1 BP1

BS2 BP11
BP1 BP2
BP2 BP3
BP3 BP4
BP4 BP5
BP5 BP6
BP6 BP7
BP7 BP8
BP8 BP9
BP9 BP10
BP10 BP11

AS1 BS2
BS1 AS2


样例输出

YES BP11 BP10 BP9 BP8 BP7 BP6 BP5 BP4 BP3 BP2 BP1 BS1 AS2 AP1 AS1 BS2

提示

没有写明提示


题目来源

鸣谢Tjz

Menuappsclose