#include<bits/stdc++.h> #define up(i,l,r) for(int i=(l);i<=(r);++i) #define down(i,l,r) for(int i=(l);i>=(r);--i) #define pi pair<int,int> #define p1 first #define p2 second #define m_p make_pair #define p_b push_back using namespace std; typedef long long ll; const int maxn=1e5+10; inline ll read(){ ll x=0;short t=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')t=-1;ch=getchar();} while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x*t; } int n,m,fa[maxn],dfn[maxn],dep[maxn],cnt; vector<int>E[maxn]; vector<pair<pi,int> >G[maxn]; vector<pi>e; int F[maxn][20]; vector<int>nd; void dfs(int u){ nd.p_b(u);dfn[u]=++cnt;F[u][0]=fa[u],dep[u]=dep[fa[u]]+1; for(int x:E[u])if(!dfn[x])fa[x]=u,dfs(x);else if(dfn[x]>dfn[u])e.p_b(m_p(u,x)); } int lca(int x,int y){ if(dep[x]>dep[y])swap(x,y); down(i,19,0)if(dep[F[y][i]]>=dep[x])y=F[y][i]; if(x==y)return x; down(i,19,0)if(F[x][i]!=F[y][i])x=F[x][i],y=F[y][i]; return F[x][0]; } int dist(int x,int y){return dep[x]+dep[y]-2*dep[lca(x,y)];} bool vis[maxn]; int ok[maxn]; bool dis[maxn]; bool reach(int u,int v){ vector<int>stk; queue<int>q;q.push(u);dis[u]=1; stk.p_b(u); while(!q.empty()){ int p=q.front();q.pop(); for(auto w:G[p]){ auto it=w.p1; if(dis[it.p1])continue; if(it.p1==v){for(int i:stk)dis[i]=0;return 1;} if(vis[it.p1])continue; dis[it.p1]=1,q.push(it.p1);stk.p_b(it.p1); } } for(int i:stk)dis[i]=0; return 0; } void dfs(int u,int p,int len,int fa){ if(vis[u]){ if(u==p){ ok[len]++; if(ok[len]>=3){printf("Yes");exit(0);} } return; } if(u!=p&&(!reach(u,p)))return; vis[u]=1; for(auto x:G[u])if(x.p1.p1>=p&&x.p2!=fa)dfs(x.p1.p1,p,len+x.p1.p2,x.p2); vis[u]=0; } void slv(){ n=read(),m=read(); up(i,1,m){ int x=read(),y=read(); E[x].p_b(y),E[y].p_b(x); } int ce=0; auto link=[&](int x,int y,int w=-1){ if(x==y)return; if(w==-1)w=dist(x,y); G[x].p_b(m_p(m_p(y,w),ce+1)); G[y].p_b(m_p(m_p(x,w),ce+1)); ++ce; }; auto solve_visual=[&](vector<int>nd){ ce=0; sort(nd.begin(),nd.end(),[](int x,int y){return dfn[x]<dfn[y];}); vector<int>ND; for(int i:nd)ND.p_b(i); up(i,0,(int)nd.size()-2)ND.p_b(lca(nd[i],nd[i+1])); sort(ND.begin(),ND.end(),[](int x,int y){return dfn[x]<dfn[y];}); nd.clear();for(int x:ND)if(nd.empty()||x!=nd.back())nd.p_b(x); up(i,0,(int)nd.size()-2)link(lca(nd[i],nd[i+1]),nd[i+1]); for(auto it:e)link(it.p1,it.p2,1); for(int i:nd)dfs(i,i,0,-1); }; auto solve=[&](int u){ nd.clear(),e.clear();dfs(u); up(i,1,19)for(int x:nd)F[x][i]=F[F[x][i-1]][i-1]; if(e.size()>2*sqrt(nd.size())){ printf("Yes\n");exit(0); } vector<int>id; for(auto it:e)id.p_b(it.p1),id.p_b(it.p2); sort(id.begin(),id.end()); id.erase(unique(id.begin(),id.end()),id.end()); solve_visual(id); }; up(i,1,n)if(!dfn[i])solve(i); printf("No"); } int main(){ //freopen("c.in","r",stdin),freopen("c.out","w",stdout); slv(); return 0; }