← 返回题目列表

AtCoder · abc232_c

F. 图同构

中文机器翻译题面 查看原题

分数: 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

下图左侧为高桥的玩具,右侧为青木的玩具。

yes1

下图显示,两个玩具的形状相同。语句中的条件满足时 例如 P = (3, 2, 1, 4)。

yes2


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

这两个玩具的形状不同。

no


示例输入 3

8 0

示例输出 3

Yes