题目描述

Takahashi 和 Aoki 分别有一种玩具，它们是通过将 $M$ 条线连接到 $N$ 个球上制作的。

在 Takahashi 的玩具中，球的编号为 $1, \\dots, N$，第 $i$ 条线连接球 $A_i$ 和 $B_i$。

同样，在 Aoki 的玩具中，球的编号为 $1, \\dots, N$，第 $i$ 条线连接球 $C_i$ 和 $D_i$。

在每个玩具中，没有线将一个球连接到自己，并且没有两个球由两条或两条以上不同的线连接。

Snuke 想知道这两个玩具是否具有相同的形状。
在这里，当满足以下条件的序列 $P$ 存在时，它们被认为具有相同的形状。

• $P$ 是 $(1, \\dots, N)$ 的一个排列。
• 对于 $1$ 到 $N$（包括 $1$ 和 $N$）之间的每对整数 $i, j$，以下条件成立。
  • 如果 Takahashi 玩具中的球 $i$ 和 $j$ 由一条线连接，则当且仅当 Aoki 玩具中的球 $P_i$ 和 $P_j$ 被一条线连接时，它们相等。

如果这两个玩具具有相同的形状，则输出 Yes；否则，输出 No。

约束条件

• $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)$
• 输入中的所有值都是整数。

输入

从标准输入读入数据，输入格式如下：

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

输出

如果这两个玩具具有相同的形状，则输出 Yes；否则，输出 No。

示例输入1

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

示例输出1

Yes

Takahashi 的玩具如下图所示（在图的左边），Aoki 的玩具如下图所示（在图的右边）。

下图显示这两个玩具具有相同的形状。例如，当 $P = (3, 2, 1, 4)$ 时，满足了题目中的条件。

示例输入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

8 0

示例输出3

Yes