4242: Graph Isomorphism

# Graph Isomorphism ### 内存 1024MB ### 时间 2S ## 题目描述 小高和小李各自有一个玩具，这个玩具由 $N$ 个球和 $M$ 根绳子组成。 在小高的玩具中，球的编号为 $1, \dots, N$，第 $i$ 根绳子连接球 $A_i$ 和球 $B_i$。 同样，在小李的玩具中，球的编号为 $1, \dots, N$，第 $i$ 根绳子连接球 $C_i$ 和球 $D_i$。 在每个玩具中，没有绳子连接球到它自身，并且任意两个球之间最多只有一根绳子连接。 现在需要计算这两个玩具是否具有相同的形状。 这里，如果存在一个序列 $P$ 满足以下条件，我们就说两个玩具具有相同的形状： - $P$ 是 $(1, \dots, N)$ 的一个排列。 - 对于任意 $1 \leq i, j \leq N$，以下条件成立： - 小高玩具中的球 $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 ``` 4 4 1 2 1 3 1 4 3 4 1 3 1 4 2 3 3 4 ``` ### 输出样例1 ``` Yes ``` ### 输入样例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 ``` ## 数据范围与提示 【样例1说明】 小高的玩具如下图左侧所示，小李的玩具如下图右侧所示。  下图显示了两个玩具是同构的。当P = (3, 2, 1, 4)时，满足题目中的条件。  【样例2说明】 这两个玩具不同构。  【数据范围】 - $1 ≤ N ≤ 8$ - $0 ≤ M ≤ N(N-1)/2$ - $1 ≤ A_i < B_i ≤ N (1 ≤ i ≤ M)$ - $(A_i, B_i) ≠ (A_j, B_j) (i ≠ j)$ - $1 ≤ C_i < D_i ≤ N (1 ≤ i ≤ M)$ - $(C_i, D_i) ≠ (C_j, D_j) (i ≠ j)$ - 所有输入均为整数。 ## 题目来源 ABC232C