#P15762. 树作业查重

树作业查重

题目描述

美术课上,老师布置了一项作业:每位学生都要画一棵美观且最重要的是原创的树。所有作品交上来后,老师开始怀疑有些同学互相抄袭。

老师认为,若可以在树 T2T_2 上添加若干个顶点和边,然后重新标号,使它变成与树 T1T_1 完全相同的树,则称树 T1T_1 可能是从树 T2T_2 抄来的。

现在老师怀疑了 tt 对学生。对于每一对给定的树,请判断第一棵树是否可能是从第二棵树抄来的。

输入格式

第一行包含一个整数 tt,表示可疑学生对数。

接下来给出 tt 组树对描述。

对于每组描述:

第一行包含一个整数 nn,表示第一棵树的顶点数。

接下来 n−1n-1 行,每行包含两个整数 u,vu,v,表示第一棵树中的一条边。

然后一行包含一个整数 mm,表示第二棵树的顶点数。

接下来 m−1m-1 行,每行包含两个整数 u,vu,v,表示第二棵树中的一条边。

输出格式

对于每一对树,输出一行一个单词:

  • 若第一棵树可能是从第二棵树抄来的,输出 Yes;
  • 否则输出 No。

输出大小写不敏感。

数据范围

  • 1≤t≤1041\le t\le 10^4;
  • 2≤n≤1052\le n\le 10^5;
  • 2≤m≤n2\le m\le n;
  • 第一棵树边的端点满足 1≤u,v≤n1\le u,v\le n;
  • 第二棵树边的端点满足 1≤u,v≤m1\le u,v\le m;
  • 所有树对中 ∑n≤5⋅105\sum n\le 5\cdot 10^5;
  • 所有树对中 ∑n⋅m≤107\sum n\cdot m\le 10^7。

样例 1

输入

2
5
1 2
1 5
2 3
2 4
4
1 2
1 3
1 4
6
1 2
1 3
1 4
5 1
6 1
4
1 2
2 3
3 4

输出

Yes
No