是一个比较无脑的算法
首先建点双，对每个点双考虑，发现点双无解当且仅当是一个环，耳分解一下非常好证明
然后只需要找到两个端点满足有三条路径即可，发现 \(\text{K4}\) 一定有解，于是缩一下广义串并联图，把缩剩下的两个点拿出来当端点跑三遍 bfs 就做完了，感觉连通性相关的图论题目每次就这些步骤啊，最多来个双极定向，这是怎么回事呢
点击查看代码
#include<bits/stdc++.h>
#include<bits/extc++.h>
#define N 200005
using namespace std;
int read(){
int w=0,h=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')h=-h;ch=getchar();}
while(ch>='0'&&ch<='9'){w=w*10+ch-'0';ch=getchar();}
return w*h;
}
struct Edge{int next,to;}edge[N<<1];
int n,m,deg[N],pre[N],head[N],num;
vector<int>G[N];bool vis[N],used[N];
__gnu_pbds::gp_hash_table<int,int>E[N],ban[N];
void add(int u,int v){edge[++num]=(Edge){head[u],v};head[u]=num;}
namespace Tarjan{
int dfn[N],low[N],tim,stk[N],top;
vector<int>DCC[N];int tot;
void tarjan(int u){
dfn[u]=low[u]=++tim;stk[++top]=u;
for(int i=head[u],v;i;i=edge[i].next)
if(!dfn[v=edge[i].to]){
tarjan(v);low[u]=min(low[u],low[v]);
if(dfn[u]==low[v]){
DCC[++tot].emplace_back(u);
while(stk[top+1]!=v)
DCC[tot].emplace_back(stk[top--]);
}
}
else low[u]=min(low[u],dfn[v]);
}
}
using namespace Tarjan;
void Solve(vector<int>dcc){
int rt=dcc[0];
for(auto u:dcc)vis[u]=true,deg[u]=0,G[u].clear(),E[u].clear();
for(auto u:dcc){
if(u==rt)continue;
for(int i=head[u],v;i;i=edge[i].next)
if(vis[v=edge[i].to]&&(u<v||v==rt)){
deg[u]++;deg[v]++;
E[u][v]=E[v][u]=true;
G[u].emplace_back(v);
G[v].emplace_back(u);
}
}
int s=0,t=0;bool flg=true;
for(auto u:dcc)flg&=(deg[u]<=2),vis[u]=false;
if(flg)return;
queue<int>q;
for(auto u:dcc)if(E[u].size()==2)q.emplace(u);
while(!q.empty()){
int u=q.front();q.pop();
if(E[u].size()!=2)continue;
vis[u]=true;
int x=(*E[u].begin()).first;
int y=(*++E[u].begin()).first;
E[u].erase(x);E[x].erase(u);
E[u].erase(y);E[y].erase(u);
if(!E[x][y])E[x][y]=E[y][x]=true;
if(E[x].size()==2)q.emplace(x);
if(E[y].size()==2)q.emplace(y);
}
for(auto u:dcc)if(!vis[u])(s==0?s=u:t=u);
auto findpath=[&](){
queue<int>q;q.push(s);
for(int i=1;i<=n;i++)vis[i]=false;
while(!q.empty()){
int u=q.front();q.pop();
if(u==t){
stk[top=1]=t;
while(u!=s){
ban[u][pre[u]]=ban[pre[u]][u]=true;
used[u=pre[u]]=true;stk[++top]=u;
}
printf("%d ",top);
for(int i=top;i>=1;i--)printf("%d ",stk[i]);
puts("");
return;
}
for(auto v:G[u])
if(!vis[v]&&!ban[u][v]&&!used[v])
vis[v]=true,pre[v]=u,q.push(v);
}
};
puts("YES");
findpath();findpath();findpath();
exit(0);
}
signed main(){
n=read();m=read();
for(int i=1,u,v;i<=m;i++)u=read(),v=read(),add(u,v),add(v,u);
for(int i=1;i<=n;i++)if(!dfn[i])tarjan(i);
for(int i=1;i<=tot;i++)Solve(DCC[i]);
puts("NO");
return 0;
}