#P18478. Anti-Plagiarism

Anti-Plagiarism

Anti-Plagiarism

美术课老师布置了一份家庭作业:每名学生都要画一棵漂亮的树,而且最重要的是,这棵树必须是原创的。收齐作业后,老师开始怀疑有些学生抄袭。

如果可以向树 T2T_2 中添加若干个(也可以是零个)顶点和边,再对顶点重新编号,使它变成与树 T1T_1 相同的树,那么老师就认为 T1T_1 可能是从 T2T_2 抄来的。

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

这里的树都是无向树。添加操作保留原有的顶点和边;原有的一条边不能被替换成经过新顶点的路径。

输入格式

第一行包含整数 tt(1≤t≤1041\le t\le 10^4),表示可疑学生对的数量。

接下来依次给出 tt 对树。每对树的描述如下:

第一行包含整数 nn(2≤n≤1052\le n\le 10^5),表示第一名学生所画的树的顶点数。接下来 n−1n-1 行,每行包含两个整数 u,vu,v(1≤u,v≤n1\le u,v\le n),表示第一棵树的一条边。

下一行包含整数 mm(2≤m≤n2\le m\le n),表示第二名学生所画的树的顶点数。接下来 m−1m-1 行,每行包含两个整数 u,vu,v(1≤u,v≤m1\le u,v\le m),表示第二棵树的一条边。

保证每份描述给出的图都是树。保证所有可疑学生对的 nn 之和不超过 5⋅1055\cdot10^5,所有 n⋅mn\cdot m 之和不超过 10710^7。

输出格式

对于每一对树,输出一行,一个单词:如果第一棵树可能是从第二棵树抄来的,输出 Yes;否则输出 No。单词的大小写不限。

原样例

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