题目描述

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

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

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

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

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

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

• $P$ 是 $(1,\ \dots,\ N)$ 的一个排列。
• 对于任意 $1 \le i,j \le 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。

输入输出样例 #1

输入 #1

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

输出 #1

Yes

输入输出样例 #2

输入 #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

输入输出样例 #3

输入 #3

8 0

输出 #3

Yes

说明/提示

样例 1 解释

小高的玩具如下图左侧所示，小李的玩具如下图右侧所示。

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

样例 2 解释

这两个玩具不同构。

数据范围

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