Graph Isomorphism

题目描述

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$（含）之间的任意整数对 $i, j$，下列条件成立。 当且仅当 Takahashi 玩具中的球 $i$ 和 $j$ 之间有绳子系着时，Aoki 玩具中的球 $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$。

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

8 0

Yes

提示

$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)$ 输入中的所有数值均为整数。Takahashi 的玩具在下图中示于左侧，Aoki 的在右侧。 下图展示了这两个玩具具有相同形状。例如，当 $P = (3, 2, 1, 4)$ 时，题目中的条件被满足。
这两个玩具不具有相同的形状。

标签: AtCoder|abc232C

来源

AtCoder|abc232C