分数: 300 点
问题陈述
高桥和青木各有一个通过附加而制成的玩具 M 电线 N 球。
在高桥的玩具中,球有编号 1, \dots, N,以及 i第 绳结 球 A_i 和 B_i.
同样,在 Aoki 的玩具中,球也有编号 1, \dots, N,以及 i第 绳结 球 C_i 和 D_i.
在每个玩具中,没有绳子将球绑在其自身上,也没有两个球被两条或更多不同的绳子绑在一起。
Snuke 想知道这两个玩具的形状是否相同。
这里,当存在序列时,它们被称为具有相同的形状 P 满足以下条件。
- P 是一个排列 (1, \dots, N).
- 对于每对整数 i, j 之间 1 和 N (含),以下内容成立。
- 球 高桥的玩具中的 i 和 j 被绳子绑住当且仅当球 青木的玩具中的 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
下图左侧为高桥的玩具,右侧为青木的玩具。

下图显示,两个玩具的形状相同。语句中的条件满足时 例如 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