1 #include<bits/stdc++.h>

 2 using namespace std;

 3 const int N=9,M=2e5+10;

 4 bool a[9][9],b[9][9];//邻接矩阵

 5 bool st[9];//全排列的标记

 6 int c[9];//记录全排列

 7 int n,m,x,y;

 8

 9 bool dfs(int u){

10     if(u==n+1){

11         for(int i=1;i<=n;i++)

12             for(int j=1;j<=n;j++)

13                 if(a[i][j]!=b[c[i]][c[j]]) return false;

14         return true;

15     }

16     for(int i=1;i<=n;i++){

17         if(!st[i]){//i未被选，可以选择i

18             st[i]=true;

19             c[u]=i;

20             if(dfs(u+1)) return true;

21             st[i]=false;//回溯取消标记

22         }

23     }

24     return false;//找不到一种合法全排列

25 }

26

27 int main(){

28     scanf("%d%d",&n,&m);

29     for(int i=1;i<=m;i++){

30         int x,y;

31         scanf("%d%d",&x,&y);

32         a[x][y]=a[y][x]=true;//有连边

33     }

34     for(int i=1;i<=m;i++){

35         int x,y;

36         scanf("%d%d",&x,&y);

37         b[x][y]=b[y][x]=1;

38     }

39     if(dfs(1)) puts("Yes\n");

40     else puts("No\n");

41     return 0;

42 }