题目描述

小明和小红各有一个由小球和绳子组成的玩具。每个玩具都有 $N$ 个小球和 $M$ 根绳子，小球分别编号为 $1$ 到 $N$。每根绳子连接两个不同的小球，同一对小球之间最多有一根绳子。

把小球看成顶点、绳子看成无向边，就得到两张无向图。现在请判断：如果只把两张图的小球重新一一对应，不增加或删除任何绳子，能否让它们的连接关系完全相同？

具体来说，你需要寻找一种一一对应的方式，使第一张图中的每个顶点都对应第二张图中一个不同的顶点，并且：

• 第一张图中直接相连的两个顶点，在第二张图中对应的两个顶点也必须直接相连。
• 第一张图中没有直接相连的两个顶点，在第二张图中对应的两个顶点也必须没有直接相连。

顶点的数字编号可以不同，图画在纸上的位置也不重要；我们只比较连接关系。满足上述条件，就称两张图“同构”。

用数学语言表示，就是存在一个 $1$ 到 $N$ 的排列 $P$，将第一张图的顶点 $i$ 对应到第二张图的顶点 $P_i$，使任意 $i,j$ 之间是否有边，与 $P_i,P_j$ 之间是否有边完全一致。

输入格式

第一行输入两个整数 $N,M$，表示每张图都有 $N$ 个顶点、$M$ 条无向边。

接下来先输入第一张图的 $M$ 条边：每行两个整数 $A_i,B_i$，表示第一张图中顶点 $A_i$ 和 $B_i$ 之间有一条边。

然后再输入第二张图的 $M$ 条边：每行两个整数 $C_i,D_i$，表示第二张图中顶点 $C_i$ 和 $D_i$ 之间有一条边。

也就是说，第一行之后共有 $2M$ 行，先给完第一张图，再给第二张图，不是把两张图的边交替输入。如果 $M=0$，输入只有第一行。

输出格式

输出一行。如果存在符合要求的一一对应方式，输出 Yes；否则输出 No。大小写必须一致。

输入样例 #1

4 4
1 2
1 3
1 4
3 4
1 3
1 4
2 3
3 4

输出样例 #1

Yes

样例解释 #1

可将第一张图的顶点 1、2、3、4，分别对应到第二张图的顶点 3、2、1、4。这样第一张图的四条边 (1,2)、(1,3)、(1,4)、(3,4)，分别对应第二张图的 (3,2)、(3,1)、(3,4)、(1,4)，连接关系完全一致，所以输出 Yes。

输入样例 #2

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

输出样例 #2

No

样例解释 #2

第一张图各顶点的度数排序后为 1、2、3、3、3；第二张图为 1、2、2、3、4。第一张图不存在度数为 4 的顶点，无法对应第二张图中度数为 4 的顶点，所以输出 No。

输入样例 #3

8 0

输出样例 #3

Yes

样例解释 #3

两张图都只有 8 个互不相连的顶点，没有任何边。任意一一对应都能保持连接关系，所以输出 Yes。

数据范围

$1\le N\le 8$，$0\le M\le \dfrac{N(N-1)}2$。

$1\le A_i<B_i\le N$，$1\le C_i<D_i\le N$。

每张图都没有自环和重复边。所有输入均为整数。

题目来源

洛谷 AT_abc232_c；AtCoder 原题。中文表述按原题规则整理。