Modern Art Plagiarism (Small)

You have photographs of two sculptures. A sculpture is made of solid metal spheres and rubber pipes, where each pipe joins two spheres. The pipes are arranged so that for any two spheres there is exactly one route between them that never uses the same pipe twice. Every sphere has the same radius and every pipe has the same length.

You suspect that the smaller of the two sculptures was made by removing some spheres and some pipes from the larger one. Write a program that decides whether that is possible.

A sculpture is described by numbering its spheres from 1 upward and listing the pairs of spheres joined by a pipe. The numbering is chosen separately for each sculpture, so the same number does not refer to the same sphere in both. The input contains several test cases.

The first line contains the number of test cases $C$.

Each test case is given in this order.

• One line with the number of spheres $N$ in the large sculpture.
• $N-1$ lines, each with two space separated integers, meaning that those two spheres of the large sculpture are joined by a pipe.
• One line with the number of spheres $M$ in the small sculpture.
• $M-1$ lines, each with two space separated integers, meaning that those two spheres of the small sculpture are joined by a pipe.

Limits

• $1 \le C \le 100$
• $2 \le N \le 8$
• $1 \le M < N$

Print $C$ lines, one per test case, in the order the test cases appear in the input. For test case $X$, print Case #X: YES if the small sculpture could have been made from the large one, or Case #X: NO if it could not. Here $X$ is the number of the test case, from 1 to $C$.

In the first test case of the sample the large sculpture is five spheres in a single line, and the small sculpture is one sphere with three other spheres attached to it. Nothing you remove from the large sculpture produces the small one.

In the second test case the small sculpture is four spheres in a single line. Matching them to spheres 2, 1, 4, 5 of the large sculpture in that order works.