102322: [AtCoder]ABC232 C - Graph Isomorphism

Problem Statement

Takahashi and Aoki each have a toy made by attaching $M$ cords to $N$ balls.

In Takahashi's toy, the balls are numbered $1, \dots, N$, and the $i$-th cord ties Ball $A_i$ and $B_i$.

Similarly, in Aoki's toy, the balls are numbered $1, \dots, N$, and the $i$-th cord ties Ball $C_i$ and $D_i$.

In each toy, no cord ties a ball to itself, and no two balls are tied by two or more different cords.

Snuke is wondering whether the two toys have the same shape.
Here, they are said to have the same shape when there is a sequence $P$ that satisfies the conditions below.

• $P$ is a permutation of $(1, \dots, N)$.
• For every pair of integers $i, j$ between $1$ and $N$ (inclusive), the following holds.
  • Balls $i$ and $j$ in Takahashi's toy are tied by a cord if and only if Balls $P_i$ and $P_j$ in Aoki's toy are tied by a cord.

If the two toys have the same shape, print Yes; otherwise, print No.

Constraints

• $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)$
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

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

Output

If the two toys have the same shape, print Yes; otherwise, print No.

Sample Input 1

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

Sample Output 1

Yes

Takahashi's toy is illustrated on the left in the figure below, and Aoki's is illustrated on the right.

The following figure shows that the two toys have the same shape. The condition in the statement is satisfied when $P = (3, 2, 1, 4)$, for example.

Sample Input 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

Sample Output 2

No

The two toys do not have the same shape.

Sample Input 3

8 0

Sample Output 3

Yes

问题描述

高桥和青木各自有一个玩具，是将$M$条绳子系在$N$个球上制作而成的。

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

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

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

スヌケ想知道这两个玩具的形状是否相同。

在这里，当存在满足以下条件的序列$P$时，称两个玩具具有相同的形状。

• $P$是$(1, \dots, N)$的排列。
• 对于$1$到$N$（含）之间的任意整数对$i, j$，以下条件成立。
• 如果高桥的玩具中球$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