Score : $300$ points

问题描述

高桥和青木各自拥有一个由 $M$ 根绳索连接 $N$ 个球的玩具。

在高桥的玩具中，球被编号为 $1, \dots, N$，第 $i$ 根绳索将球 $A_i$ 和 $B_i$ 连接在一起。

类似地，在青木的玩具中，球也被编号为 $1, \dots, N$，第 $i$ 根绳索将球 $C_i$ 和 $D_i$ 连接在一起。

在每个玩具中，没有绳索会将一个球与自身相连，也没有两个球会被两条或更多的不同绳索相连。

Snuke 正在思考这两个玩具是否具有相同的形状。
这里，若满足以下条件，则认为它们具有相同的形状：

• 序列 $P$ 是 $(1, \dots, N)$ 的一个排列。
• 对于每一对整数 $i, j$ 在 $1$ 到 $N$（包括两端点）之间，满足以下条件：
  • 高桥玩具中的球 $i$ 和 $j$ 若由一根绳索相连，则青木玩具中的球 $P_i$ 和 $P_j$ 也必须由一根绳索相连。

如果两个玩具具有相同的形状，则输出 Yes；否则，输出 No。

以上为通义千问 qwen-max 翻译，仅供参考。

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

update @ 2024/3/10 10:06:31