/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 300 点
問題文
高橋君と青木君は、それぞれ N 個のボールに M 本のひもを取り付けたおもちゃを持っています。
高橋君のおもちゃにおいて、ボールには 1, \dots, N と番号が付けられており、i \, (1 \leq i \leq M) 本目のひもはボール A_i とボール B_i を結んでいます。
青木君のおもちゃにおいても同様に、ボールには 1, \dots, N と番号が付けられており、i \, (1 \leq i \leq M) 本目のひもはボール C_i とボール D_i を結んでいます。
それぞれのおもちゃにおいて、同一のボールを結ぶようなひもは存在せず、2 つのボールを 2 本以上の異なるひもが結んでいることはありません。
すぬけ君は、2 人のおもちゃが同じ形であるかどうか気になっています。
ここで、2 人のおもちゃが同じ形であるとは、以下の条件を満たす数列 P が存在することをいいます。
- P は (1, \dots, N) を並べ替えて得られる。
- 任意の 1 以上 N 以下の整数 i, j に対し、以下が成り立つ。
- 高橋君のおもちゃにおいてボール i, j がひもで繋がれていることと、青木君のおもちゃにおいてボール P_i, P_j がひもで繋がれていることは同値である。
2 人のおもちゃが同じ形であるなら 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
出力
2 人のおもちゃが同じ形であるなら Yes、そうでないなら No と出力せよ。
入力例 1
4 4 1 2 1 3 1 4 3 4 1 3 1 4 2 3 3 4
出力例 1
Yes
高橋君のおもちゃは下図の左側のような形をしており、青木君のおもちゃは下図の右側のような形をしています。
次の図から、2 人のおもちゃが同じ形であることがわかります。例えば 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
2 人のおもちゃは同じ形ではありません。
入力例 3
8 0
出力例 3
Yes
Score : 300 points
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