Modern Art Plagiarism 树同构

时间限制:3s      空间限制:128MB

题目描述

定义树A与B同构,当且仅当树A的顶点经过一定的重新标号,树A的顶点集合边集完全与树B一一对应。
Your Task
给定两棵树T1与T2,判断是否存在T1的子树T3,使得T3与T1同构。


输入格式

第一行T表示数据组数
对于每组数据,第一行n表示T1的点数
接下来n-1行每行a b描述T1的一条边
接下来一行m表示T2的点数
再接下来m-1行每行a b描述T2的一条边


输出格式

对于每组数据,在一行中输出YES表示存在T3,NO表示不存在


样例输入

51 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

提示

样例解释
 第一组数据中T2的点1度数为3,而T1是一条链,没有度数为3的点,显然NO。
 第二组数据中T2是一条4个点的链,与T1中的2-1-4-5同构。


数据范围

 100%:T≤10,1≤m<=N<=100


题目来源

google code jam 2008 APAC Onsites