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 \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 翻译