{"problem":{"name":"Graph Isomorphism","description":{"content":"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 Aok","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc232_c"},"statements":[{"statement_type":"Markdown","content":"Takahashi and Aoki each have a toy made by attaching $M$ cords to $N$ balls.\nIn Takahashi's toy, the balls are numbered $1, \\dots, N$, and the $i$\\-th cord ties Ball $A_i$ and $B_i$.\nSimilarly, in Aoki's toy, the balls are numbered $1, \\dots, N$, and the $i$\\-th cord ties Ball $C_i$ and $D_i$.\nIn each toy, no cord ties a ball to itself, and no two balls are tied by two or more different cords.\nSnuke is wondering whether the two toys have the same shape.  \nHere, they are said to have the same shape when there is a sequence $P$ that satisfies the conditions below.\n\n*   $P$ is a permutation of $(1, \\dots, N)$.\n*   For every pair of integers $i, j$ between $1$ and $N$ (inclusive), the following holds.\n    *   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.\n\nIf the two toys have the same shape, print `Yes`; otherwise, print `No`.\n\n## Constraints\n\n*   $1 \\leq N \\leq 8$\n*   $0 \\leq M \\leq \\frac{N(N - 1)}{2}$\n*   $1 \\leq A_i \\lt B_i \\leq N \\, (1 \\leq i \\leq M)$\n*   $(A_i, B_i) \\neq (A_j, B_j) \\, (i \\neq j)$\n*   $1 \\leq C_i \\lt D_i \\leq N \\, (1 \\leq i \\leq M)$\n*   $(C_i, D_i) \\neq (C_j, D_j) \\, (i \\neq j)$\n*   All values in input are integers.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$ $M$\n$A_1$ $B_1$\n$\\vdots$\n$A_M$ $B_M$\n$C_1$ $D_1$\n$\\vdots$\n$C_M$ $D_M$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc232_c","tags":[],"sample_group":[["4 4\n1 2\n1 3\n1 4\n3 4\n1 3\n1 4\n2 3\n3 4","Yes\n\nTakahashi's toy is illustrated on the left in the figure below, and Aoki's is illustrated on the right.\n![image](https://img.atcoder.jp/ghi/abc232c_yes1.jpg)\nThe 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.\n![image](https://img.atcoder.jp/ghi/abc232c_yes2.jpg)"],["5 6\n1 2\n1 3\n1 4\n3 4\n3 5\n4 5\n1 2\n1 3\n1 4\n1 5\n3 5\n4 5","No\n\nThe two toys do not have the same shape.\n![image](https://img.atcoder.jp/ghi/abc232c_no.jpg)"],["8 0","Yes"]],"created_at":"2026-03-03 11:01:14"}}