题目描述

定义树 $A$ 与 $B$ 同构，当且仅当树 $A$ 的顶点经过一定的重新标号，树 $A$ 的顶点集合边集完全与树 $B$ 一一对应。

Your Task：给定两棵树 $T_1$ 与 $T_2$，判断是否存在 $T_1$ 的子树 $T_3$，使得 $T_3$ 与 $T_2$ 同构。

（注：这里的子树指的是树上的一个联通子图）

输入格式

本题有多组数据。

第一行 $T$ 表示数据组数。

对于每组数据，第一行 $n$ 表示 $T_1$ 的点数。

接下来 $n-1$ 行每行两个整数 $a,b$ 描述 $T_1$ 的一条边。

接下来一行 $m$ 表示 $T_2$ 的点数。

再接下来 $m-1$ 行每行两个整数 $a,b$ 描述 $T_2$ 的一条边。

输出格式

对于每组数据，在一行中输出 YES 表示存在 $T_3$ 与 $T_2$ 同构，NO 表示不存在。

样例输入

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

样例输出

NO
YES

样例说明

第一组数据中 $T_2$ 的点 $1$ 度数为 $3$，而 $T_1$是一条链，没有度数为 $3$ 的点，显然 NO。

第二组数据中 $T_2$ 是一条 $4$ 个点的链，与 $T_1$ 中的 $2-1-4-5$ 同构。

数据规模与约定

对于 $100\%$ 的数据：$T\le 10，1\le m\le n\le 100$。

题目来源

google code jam 2008 APAC Onsites