Description

高桥和青木各有一个用 $M$ 根绳子绑在 $N$ 个球上做成的玩具。

在高桥的玩具中，球的编号是 $1, \dots, N$ ，第 $i$ 条绳子系着球 $A_i$ 和 $B_i$ 。

同样，在青木的玩具中，球的编号是 $1, \dots, N$ ，第 $i$ 条绳子系着球 $C_i$ 和 $D_i$ 。

在每个玩具中，没有一条绳子将一个球与自己绑在一起，也没有两个球被两条或两条以上不同的绳子绑在一起。

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

• $P$ 是 $(1, \dots, N)$ 的排列。
• 对于介于 $1$ 与 $N$ 之间的每一对整数 $i, j$ 都成立一下这个条件即：。
  • 当且仅当青木玩具中的球 $P_i$ 和 $P_j$ 用绳子系住时，高桥玩具中的球 $i$ 和 $j$ 用绳子系住。

如果两个玩具的形状相同，则打印 Yes；否则打印 No。

Format

Input

第一行输入两个空格隔开的整数 $N,M$

接下来 $M$ 行每行两个整数代表 $A_i,B_i$

接下来 $M$ 行每行两个整数代表 $C_i,D_i$

Output

如果两个玩具的形状相同，则打印 Yes；否则，打印 No。

Samples

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

0 0

Yes

样例 1 解释

下图左边是高桥的玩具，右边是青木的玩具。

如下图所示，两个玩具的形状相同。例如，当 $P = (3, 2, 1, 4)$ 时，声明中的条件得到满足。

样例 2 解释

这两个玩具的形状不一样。

Limitation

• $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)$
• 输入值均为整数。