Description

你有两座雕塑的图片。这些雕塑由若干个实心金属球体组成，并且有一些橡胶管连接着成对的球体。每座雕塑中的管道连接方式保证，对于任意一对球体，沿着一系列管道（不重复经过任何管道）恰好有一条路径可以连接这两个球体。所有球体的半径都相同，所有管道的长度也都相同。

你怀疑较小的雕塑实际上是通过从较大的雕塑中移除一些球体和管道得到的。你想编写一个程序来判断这种情况是否可能。

输入包含若干组测试数据。一座雕塑的描述方式是：将球体从 $1$ 开始连续编号，并列出所有通过管道连接的球体对。每座雕塑的编号方式是独立选择的。

Input Format

• 第一行包含一个整数 $C$，表示测试数据的组数。

对于每组测试数据，包含如下内容：

• 一行包含整数 $N$，表示大雕塑中的球体数量。
• 接下来的 $N-1$ 行，每行包含两个用空格分隔的整数，表示大雕塑中通过管道连接的两个球体的编号。
• 一行包含整数 $M$，表示小雕塑中的球体数量。
• 接下来的 $M-1$ 行，每行包含两个用空格分隔的整数，表示小雕塑中通过管道连接的两个球体的编号。

Output Format

• 共 $C$ 行，每行对应输入文件中的一组测试数据，格式为 "Case #$X$: YES"（如果第 $X$ 组数据中的小雕塑可以通过从大雕塑中移除部分球体和管道得到），或 "Case #$X$: NO"（否则）。其中 $X$ 为测试数据编号，范围为 $1$ 到 $C$。

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

Case #1: NO
Case #2: YES

Hint

样例解释

在第一个样例中，大雕塑有五个球体连成一条直线，而小雕塑有一个球体与另外三个球体相连。无法通过从大雕塑中移除部分球体和管道得到小雕塑。

在第二个样例中，小雕塑是四个球体连成一条直线。可以对应大雕塑中的球体 $2-1-4-5$。

数据范围

小数据集（7 分，测试点 1 - 可见）

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

大数据集（25 分，测试点 2 - 隐藏）

• $1 \leq C \leq 50$
• $2 \leq N \leq 100$
• $1 \leq M < N$

由 ChatGPT 4.1 翻译