AT_abc232_c [ABC232C] Graph Isomorphism

题目描述

高桥君和青木君各自拥有一个由 $N$ 个球和 $M$ 根绳子组成的玩具。

在高桥君的玩具中，球被编号为 $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。

输入格式

输入以如下格式从标准输入读入。

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

输出格式

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

输入输出样例 #1

输入 #1

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

输出 #1

Yes

输入输出样例 #2

输入 #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

输入 #3

8 0

输出 #3

Yes

说明/提示

限制条件

• $1 \leq N \leq 8$
• $0 \leq M \leq \frac{N(N-1)}{2}$
• $1 \leq A_i < B_i \leq N\quad (1 \leq i \leq M)$
• $(A_i, B_i) \neq (A_j, B_j)\quad (i \neq j)$
• $1 \leq C_i < D_i \leq N\quad (1 \leq i \leq M)$
• $(C_i, D_i) \neq (C_j, D_j)\quad (i \neq j)$
• 所有输入均为整数。

样例解释 1

高桥君的玩具如左图所示，青木君的玩具如右图所示。

从下图可以看出，两个人的玩具具有相同的形状。例如，取 $P=(3,2,1,4)$ 时，满足题目中的条件。

样例解释 2

两个人的玩具形状不同。

由 ChatGPT 4.1 翻译