#P18478. Anti-Plagiarism
Anti-Plagiarism
Anti-Plagiarism
美术课老师布置了一份家庭作业:每名学生都要画一棵漂亮的树,而且最重要的是,这棵树必须是原创的。收齐作业后,老师开始怀疑有些学生抄袭。
如果可以向树 中添加若干个(也可以是零个)顶点和边,再对顶点重新编号,使它变成与树 相同的树,那么老师就认为 可能是从 抄来的。
老师一共怀疑 对学生。对于每一对给定的树,判断第一棵树是否可能是从第二棵树抄来的。
这里的树都是无向树。添加操作保留原有的顶点和边;原有的一条边不能被替换成经过新顶点的路径。
输入格式
第一行包含整数 (),表示可疑学生对的数量。
接下来依次给出 对树。每对树的描述如下:
第一行包含整数 (),表示第一名学生所画的树的顶点数。接下来 行,每行包含两个整数 (),表示第一棵树的一条边。
下一行包含整数 (),表示第二名学生所画的树的顶点数。接下来 行,每行包含两个整数 (),表示第二棵树的一条边。
保证每份描述给出的图都是树。保证所有可疑学生对的 之和不超过 ,所有 之和不超过 。
输出格式
对于每一对树,输出一行,一个单词:如果第一棵树可能是从第二棵树抄来的,输出 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