图的同构

题目描述

高桥君和青木君各有一个由 $N$ 个球和 $M$ 根绳连接而成的玩具。

在高桥君的玩具中,球被编号为 $1, \dots, N$,第 $i$ 根绳连接球 $A_i$ 和球 $B_i$。

同样,在青木君的玩具中,球被编号为 $1, \dots, N$,第 $i$ 根绳连接球 $C_i$ 和球 $D_i$。

在每个玩具中,没有绳将球与自身相连,也没有两根及以上的绳连接同一对球。

Snuke 君想知道两个玩具的形状是否相同。

这里,当存在满足以下条件的排列 $P$ 时,称两个玩具形状相同。

• $P$ 是 $(1, \dots, N)$ 的一个排列。
• 对于满足 $1 \le i, j \le N$ 的每一对整数 $i, j$,下面条件成立。

高桥君玩具中的球 $i$ 和球 $j$ 由绳相连,当且仅当青木君玩具中的球 $P_i$ 和球 $P_j$ 由绳相连。

如果两个玩具形状相同,输出 Yes;否则输出 No。

输入格式

输入按以下格式从标准输入给出：

$N$ $M$
$A_1$ $B_1$
$\vdots$
$A_M$ $B_M$
$C_1$ $D_1$
$\vdots$
$C_M$ $D_M$

输出格式

如果两个玩具形状相同,输出 Yes;否则输出 No。

样例

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

Yes

高桥君的玩具如下图左所示,青木君的如下图右所示。

下图表明两个玩具形状相同。例如,当 $P = (3, 2, 1, 4)$ 时满足题面中的条件。

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

No

两个玩具形状不相同。

8 0

Yes

数据范围

• $1 \le N \le 8$
• $0 \le M \le \frac{N(N - 1)}{2}$
• $1 \le A_i \lt B_i \le N \, (1 \le i \le M)$
• $(A_i, B_i) \neq (A_j, B_j) \, (i \neq j)$
• $1 \le C_i \lt D_i \le N \, (1 \le i \le M)$
• $(C_i, D_i) \neq (C_j, D_j) \, (i \neq j)$
• 输入均为整数