P15486 [CERC2012] Graphic Madness

在比特国，有两家领先的显卡制造商：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$ 个不同的节点。每两个相邻的节点必须通过线路或电缆连接。此外，第一个节点和最后一个节点也必须相连。

翻译由 DeepSeek 完成