题目描述

小高和小李各自有一个玩具，这个玩具由 $N$ 个球和 $M$ 根绳子组成。

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

同样，在小李的玩具中，球的编号为 $1, \dots, N$，第 $i$ 根绳子连接球 $C_i$ 和球 $D_i$。

在每个玩具中，没有绳子连接球到它自身，并且任意两个球之间最多只有一根绳子连接。

现在需要计算这两个玩具是否具有相同的形状。

这里，如果存在一个序列 $P$ 满足以下条件，我们就说两个玩具具有相同的形状：

• $P$ 是 $(1, \dots, N)$ 的一个排列。

• 对于任意 $1 \leq i, j \leq N$，以下条件成立：

  • 小高玩具中的球 $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

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说明】
小高的玩具如下图左侧所示，小李的玩具如下图右侧所示。

下图显示了两个玩具是同构的。当P = (3, 2, 1, 4)时，满足题目中的条件。

【样例2说明】
这两个玩具不同构。

数据范围

• $1 ≤ N ≤ 8$
• $0 ≤ M ≤ N(N-1)/2$
• $1 ≤ A_i < B_i ≤ N (1 ≤ i ≤ M)$
• $(A_i, B_i) ≠ (A_j, B_j) (i ≠ j)$
• $1 ≤ C_i < D_i ≤ N (1 ≤ i ≤ M)$
• $(C_i, D_i) ≠ (C_j, D_j) (i ≠ j)$
• 所有输入均为整数。

来源

• AtCoder ABC232C