#include <bits/stdc++.h> #define pii pair<int,int> #define fi first #define se second #define mk make_pair #define ll long long #define ull unsigned long long #define uint unsigned int #define bi __int128_t #define lb(x) ((x)&(-(x))) #define gp(i,j) (((i)>>(j-1))&1) #define ppc __builtin_popcount #define db long double using namespace std; const int N=550,M=3e4+10,mod=998244353,iv2=(mod+1)/2; const int inf=1e9+10; void Add(int &a,int b){a+=b;if(a>=mod) a-=mod;} void Sub(int &a,int b){a-=b;if(a<0) a+=mod;} void Mul(int &a,int b){a=1ll*a*b%mod;} vector<pii> E[N],edge; vector<int> G[M]; int fa[M][22],dep[M],bel[M],dfn[M],w[M],dc=0; int clen[M]; bool vis[N],vis1[N],vis2[N],app[M],invt[M]; int cnt[M]; bool dfs2(int u,int to){ if(u==to) return 1; //vis2[u]=1; for(auto ed:E[u]){ int v=ed.fi,id=ed.se; if(vis2[id]||vis1[id]) continue; if(vis[v]&&v!=to) continue; vis2[id]=1; if(dfs2(v,to)) return 1; }return 0; } bool ok=0; void dfs1(int u,int st,int len,int len2,int la=-1){ if(ok||u<st) return ; memset(vis2,0,sizeof(vis2)); if(!dfs2(u,st)) return ; vis[u]=1; //cout<<":"<<u<<' '<<len<<' '<<len2<<endl; for(auto ed:E[u]){ int v=ed.fi,id=ed.se; if(id==la) continue; if(v==st){ //cout<<len+w[id]<<' '<<len2<<' '<<id<<' '<<st<<endl; if(cnt[len+w[id]]>=2&&len+w[id]!=2){ ok=1;return ; } if(cnt[len+w[id]]&&clen[len+w[id]]!=len2){ ok=1;return ; } cnt[len+w[id]]++; clen[len+w[id]]=len2; } if(vis[v]||vis1[id]) continue; vis1[id]=1; dfs1(v,st,len+w[id],len2+1,id); vis1[id]=0; } vis[u]=0; } void dfs(int u,int pa){ app[u]=1;fa[u][0]=pa;dep[u]=dep[pa]+1;dfn[u]=++dc; for(int i=1;i<=19;i++) fa[u][i]=fa[fa[u][i-1]][i-1]; for(auto v:G[u]){ if(v==pa) continue; if(app[v]){ //cout<<u<<' '<<v<<' '<<invt[1]<<endl; invt[u]=1;invt[v]=1; edge.push_back(mk(u,v)); }else{ dfs(v,u); } } } bool clr[M]; void color(int u){ clr[u]=1; for(auto v:G[u]){ if(clr[v]) continue; color(v); } } int lca(int x,int y){ if(dep[x]<dep[y]) swap(x,y); for(int i=19;i>=0;i--) if(dep[fa[x][i]]>=dep[y]) x=fa[x][i]; if(x==y) return x; for(int i=19;i>=0;i--) if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i]; return fa[x][0]; } int n,m; int main(){ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); cin>>n>>m; for(int i=1;i<=m;i++){ int u,v;cin>>u>>v; G[u].push_back(v); G[v].push_back(u); } for(int i=1;i<=n;i++){ if(clr[i]) continue; G[n+1].push_back(i); G[i].push_back(n+1); color(i);m++; }//cout<<m<<endl; if(m>n+2*sqrt(n)+13){ cout<<"Yes"<<endl; return 0; }else{ dfs(n+1,0); vector<int> node,vt; for(int i=1;i<=n;i++) if(invt[i]) node.push_back(i),vt.push_back(i); //for(int i=1;i<=n;i++) cout<<invt[i]<<' '; sort(node.begin(),node.end(), [&](int x,int y){return dfn[x]<dfn[y];}); for(int i=1;i<node.size();i++){ //cout<<lca(node[i-1],node[i])<<endl; vt.push_back(lca(node[i-1],node[i])); } sort(vt.begin(),vt.end(), [&](int x,int y){return dfn[x]<dfn[y];}); if(!vt.empty()) bel[vt[0]]=1;int tot=1,cnt=0; //cout<<vt[0]<<endl; for(int i=1;i<vt.size();i++){ if(vt[i]!=vt[i-1]){ //cout<<vt[i-1]<<' '; bel[vt[i]]=++tot;//cout<<node.size()<<endl; int lc=lca(vt[i],vt[i-1]); int dis=dep[vt[i]]-dep[lc]; ++cnt;w[cnt]=dis; E[tot].push_back(mk(bel[lc],cnt)); E[bel[lc]].push_back(mk(tot,cnt)); //cout<<tot<<' '<<bel[lc]<<endl; } } //cout<<"OK"<<cnt<<' '<<tot<<endl; for(auto ed:edge){ ++cnt;w[cnt]=1;//cout<<bel[ed.fi]<<' '<<bel[ed.se]<<endl; E[bel[ed.fi]].push_back(mk(bel[ed.se],cnt)); //E[bel[ed.se]].push_back(mk(bel[ed.fi],cnt)); } for(int i=1;i<=tot;i++){ dfs1(i,i,0,1); if(ok) break; }if(ok) cout<<"Yes"<<endl;else cout<<"No"<<endl; /*for(int i=1;i<=tot;i++){ for(auto ed:E[i]){ cout<<i<<' '<<ed.fi<<' '<<w[ed.se]<<endl; } }*/ } cout.flush(); return 0; }