套路的，先随便找这张图的一棵生成树，原条件等价于存在一条路径同时被两条非树边覆盖。
直接枚举非树边进行覆盖，发现如果只要有一条树边的覆盖次数达到了 2 就可以退出了。因此，我们选取这张图的 dfs 树作为我们的生成树。
这样做有一个很好的性质：非树边只会是返租边或是前向边。由于这是一张无向图，前向边就是返租边。因此只需要记每条树边被哪条非树边覆盖，暴力向上跳即可。时间复杂度 \(\mathcal{O}(n+m)\)。
补个图：
这张图中 \((e,c)\) 间就有三条路径：\(e\to d\to c\)，\(e\to a\to c\) 和 \(e\to f\to b\to c\)。
还有一个细节：一条返祖边经过的树边中可能有多条被不同的其他返祖边覆盖过，遇到这种情况直接选一类即可。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
inline int read(){
int x=0,f=1;char ch=getchar();
while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
return x*f;
}
struct edge{
int v,w,nxt;
}e[400005];
int tot,head[200005];
void add(int u,int v,int w){
e[++tot]=(edge){v,w,head[u]},head[u]=tot;
}
int dep[200005],Fa[200005],vis[200005],Tree[200005];
void dfs(int u,int fa){
dep[u]=dep[fa]+1,Fa[u]=fa,vis[u]=1;
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].v,w=e[i].w;if(v==fa||vis[v])continue;
Tree[w]=1;dfs(v,u);
}
}
int g[200005],up[200005],down[200005];
int jump(int u,int v,int col){
if(dep[u]>dep[v])swap(u,v);
up[col]=u,down[col]=v;
vector<int>tmp;int id=-1;
while(v!=u){
if(g[v]&&(id==-1||g[v]==id))tmp.push_back(v),id=g[v];
g[v]=col,v=Fa[v];
}
if(id==-1)return 0;
puts("YES");
printf("%d ",(int)tmp.size()+1);
printf("%d ",Fa[tmp.back()]);
for(int i=(int)tmp.size()-1;i>=0;i--)printf("%d ",tmp[i]);
puts("");
int s=Fa[tmp.back()],t=Fa[tmp.back()],p=tmp.front();
tmp.clear();while(s!=up[id])tmp.push_back(s),s=Fa[s];
tmp.push_back(up[id]),s=down[id];
while(s!=p)tmp.push_back(s),s=Fa[s];
tmp.push_back(p);
printf("%d ",(int)tmp.size());
for(auto x:tmp)printf("%d ",x);
puts("");
tmp.clear();while(t!=up[col])tmp.push_back(t),t=Fa[t];
tmp.push_back(up[col]),t=down[col];
while(t!=p)tmp.push_back(t),t=Fa[t];
tmp.push_back(p);
printf("%d ",(int)tmp.size());
for(auto x:tmp)printf("%d ",x);
puts("");
return 1;
}
struct Graph{
int u,v;
}q[200005];
signed main(){
int n=read(),m=read();
for(int i=1,u,v;i<=m;i++)u=read(),v=read(),add(u,v,i),add(v,u,i),q[i]=(Graph){u,v};
for(int i=1;i<=n;i++)if(!vis[i])dfs(i,0);
for(int i=1;i<=m;i++)if(!Tree[i]&&jump(q[i].u,q[i].v,i))return 0;
puts("NO");
return 0;
}