说明

在比特国，有两家领先的显卡制造商：Bitotronics 和 3D-Bytes。它们的高端显卡非常相似。每张显卡都由许多节点组成，节点之间通过传输正在处理信号的线路连接。产品包含两种节点：插座和处理器。线路网络满足以下条件：

• 每个插座恰好连接到一个处理器，且不与其他插座相连。
• 每个处理器至少连接到其他两个节点。
• 网络中任意两个节点之间恰好存在一条由线路构成的路径。换句话说，节点之间的连接图是一棵树。

比特尤喜欢摆弄电脑硬件。他买了两个显卡，每家制造商各一个。由于两张卡恰好有相同数量的插座，他决定用电缆将 Bitotronics 卡的每个插座分别连接到 3D-Bytes 卡的不同插座上。他得到的设备如下图所示：

比特尤希望从该设备中榨取出最大处理能力。为此，他想找到一条路径，使得被处理的信号可以沿着线路和电缆传输。这条路径应恰好访问两张卡的每个节点一次，并且起点和终点必须在同一张卡的同一个节点上。帮助比特尤判断这是否可行。

输入格式

输入的第一行包含测试用例的数量 $T$。随后是每个测试用例的描述：

每个测试用例以三个整数 $k, n, m$ 开头（$2\le k\le 1000$，$1\le n,m\le 1000$），分别表示每张卡上的插座数量、Bitotronics 卡上的处理器数量以及 3D-Bytes 卡上的处理器数量。卡上的节点命名如下：

• Bitotronics 卡的插座：$AS1, AS2, \dots, ASk$
• Bitotronics 卡的处理器：$AP1, AP2, \dots, APn$
• 3D-Bytes 卡的插座：$BS1, BS2, \dots, BSk$
• 3D-Bytes 卡的处理器：$BP1, BP2, \dots, BPm$

接下来的 $n+k-1$ 行包含 Bitotronics 卡上线路网络的描述。每行包含该卡上由一条线路直接连接的两个不同节点的名称。该描述之后是一个空行。接下来的 $m+k-1$ 行以相同格式包含 3D-Bytes 卡上线路网络的描述。该描述之后是另一个空行。测试用例的最后 $k$ 行描述比特尤添加的电缆。每行包含由电缆直接连接的两张卡上的两个插座名称。每个插座恰好出现在这 $k$ 行中的一行。除最后一个测试用例之外，每个测试用例之后都有一个空行。

输出格式

按照输入中出现的顺序输出每个测试用例的答案。对于每个测试用例，输出一行答案。如果不存在满足要求的路径，则输出 NO。否则，输出 YES 并接着输出路径的描述：按信号经过的顺序列出 $n+m+2k$ 个不同的节点。每两个相邻的节点必须通过线路或电缆连接。此外，第一个节点和最后一个节点也必须相连。

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

提示

翻译由 DeepSeek 完成