Under construction

Still being built. Things may change

Modern Art Plagiarism (Small)

Interview

Time limit5sMemory limit512 MB

Summary
Decide whether the smaller tree is a connected subgraph of the larger tree, with only the shapes mattering, not the original labels.
Level

Easy3 of 10

Topics
Tree, Backtracking
Solved
No attempts yet

Problem

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.

Input

The first line contains the number of test cases CC.

Each test case is given in this order.

  • One line with the number of spheres NN in the large sculpture.
  • N−1N-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 MM in the small sculpture.
  • M−1M-1 lines, each with two space separated integers, meaning that those two spheres of the small sculpture are joined by a pipe.

Limits

  • 1≤C≤1001 \le C \le 100
  • 2≤N≤82 \le N \le 8
  • 1≤M<N1 \le M < N

Output

Print CC lines, one per test case, in the order the test cases appear in the input. For test case XX, 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 XX is the number of the test case, from 1 to CC.

Hint

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.

Examples3

  1. Example 1

    Input
    2
5
1 2
2 3
3 4
4 5
4
1 2
1 3
1 4
5
1 2
1 3
1 4
4 5
4
1 2
2 3
3 4
    Expected output
    Case #1: NO
Case #2: YES

  2. Example 2

    Input
    1
2
1 2
1
    Expected output
    Case #1: YES

  3. Example 3

    Input
    5
8
1 2
1 3
1 4
1 5
1 6
1 7
1 8
3
1 2
2 3
8
1 2
1 3
1 4
1 5
1 6
1 7
1 8
7
1 2
1 3
1 4
1 5
1 6
1 7
8
1 2
2 3
3 4
4 5
5 6
6 7
7 8
7
1 2
2 3
3 4
4 5
5 6
6 7
8
1 2
2 3
3 4
4 5
5 6
6 7
7 8
4
1 2
1 3
1 4
5
1 2
1 3
1 4
1 5
2
1 2
    Expected output
    Case #1: YES
Case #2: YES
Case #3: YES
Case #4: NO
Case #5: YES