|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|1 초||128 MB||24||9||9||47.368%|
In Byteland, there are two leading video card manufacturers: Bitotronics and 3D-Bytes. Their top-of-the-line cards are quite similar. Each of them consists of many nodes, connected with wires transferring the signal that is being processed. The products contain two kinds of nodes: sockets and processors. The wire network fulfills the following conditions:
Bitthew loves to tinker with computer hardware. He has bought two video cards, one from each manufacturer. Since accidentally the cards have the same number of sockets, he has decided to connect each socket of the Bitotronics card to a distinct socket of the 3D-Bytes card with cables. The device he obtained looks like this:
Bitthew would like to squeeze out maximum processing power from the device. In order to do that, he wants to find a path through wires and cables that the processed signal can take. The path should visit each node of both cards exactly once, and it should start and end at the same node on the same card. Help Bitthew find out whether this can be done.
The first line of the input contains the number of test cases T. The descriptions of the test cases follow:
Each test case starts with three integers k, n, m (2 ≤ k ≤ 1 000, 1 ≤ n, m ≤ 1 000) denoting respectively the number of sockets on each card, the number of processors on the Bitotronics card, and the number of processors on the 3D-Bytes card. The nodes on the cards are named as follows:
The next n + k − 1 lines contain the description of the wire network on the Bitotronics card. Each of these lines contains the names of two different nodes on that card that are connected directly by a wire. The description is followed by a blank line. The next m + k − 1 lines contain the description of the wire network on the 3D-Bytes card in the same format. The description is followed by another blank line. The last k lines of the test case describe the cables added by Bitthew. Each of these lines contains the names of two sockets on different cards that are directly connected by a cable. Every socket will be present on exactly one of these k lines. There is a blank line after each test case except the last one.
Print the answers to the test cases in the order in which they appear in the input. For each test case print a single line containing the answer. If there exists no path with the desired properties, output NO. Otherwise, output YES followed by a description of the path: n+m+2k distinct nodes in the order in which the signal will pass through them. Every two consecutive nodes should be connected by a wire or a cable. Additionally, the first and the last node must be connected.
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