题目链接：E. Cycling City
题目大意：洛谷
题解：经过翻题解画图可以发现，一张图不存在这样的路径当且仅当这张图是一个沙漠。如何判断一张联通图是不是仙人掌很简单，任意求出一棵生成树后，将不在生成树上的边加 1 ，如果没有权值超过 1 的边，那么这一张图就是一个仙人掌。
那么接下来的主要问题就是如何构造答案，思路比较清晰，就是找出任意两个环相交的一条链，这一条链很明显可以通过三种方式找到，所以接下来的问题就是怎么找这一条链以及这两个环，首先，我们找到在上一个步骤中权值大于 1 的，在生成树上深度最小的边，选取最小的边的原因是在它一定会是最终答案的那条链的起点，然后暴力往下找到任意两个环，记录环中深度最小的点和深度最大的点（你也可以理解为记录环上唯一一条不在生成树上的边），然后链的终点就是两个环上深度最大的点的 LCA ，这里直接暴力就可以了，然后路径就非常好找了，因为大部分的边都在生成树上，唯二不在生成树上的边已经被记录下来了。
时间复杂度(O(n))。
代码：
#include <vector>
#include <cstdio>
#include <algorithm>
using namespace std;
void read(int &a){
a=0;
char c=getchar();
while(c<'0'||c>'9'){
c=getchar();
}
while(c>='0'&&c<='9'){
a=(a<<1)+(a<<3)+(c^48);
c=getchar();
}
}
const int Maxn=200000;
int head[Maxn+5],arrive[Maxn<<1|5],nxt[Maxn<<1|5],tot;
void add_edge(int from,int to){
arrive[++tot]=to;
nxt[tot]=head[from];
head[from]=tot;
}
int n,m;
int sum[Maxn+5];
int fa[Maxn+5];
int dep[Maxn+5];
void init_dfs(int u){
dep[u]=dep[fa[u]]+1;
for(int i=head[u];i;i=nxt[i]){
int v=arrive[i];
if(v==fa[u]){
continue;
}
if(dep[v]==0){
fa[v]=u;
init_dfs(v);
sum[u]+=sum[v];
}
else if(dep[v]<dep[u]){
sum[u]++;
sum[v]--;
}
}
}
int start,bottom;
struct Edge{
int u,v;
}edge[5];
int len;
void work_dfs(int u){
for(int i=head[u];i;i=nxt[i]){
int v=arrive[i];
if(v==fa[u]){
continue;
}
if(dep[v]==dep[u]+1){
work_dfs(v);
}
else if(dep[v]<dep[start]){
edge[++len].u=u;
edge[len].v=v;
}
if(len>=2){
break;
}
}
}
vector<int> ans[3];
void calc_path(int u,int v,vector<int>& ans){
static vector<int> path;
path.clear();
bool flag=0;
if(dep[u]<dep[v]){
swap(u,v);
flag=1;
}
while(u!=v){
path.push_back(u);
u=fa[u];
}
path.push_back(v);
if(flag){
reverse(path.begin(),path.end());
}
for(int i=0;i<(int)path.size();i++){
ans.push_back(path[i]);
}
}
int main(){
read(n),read(m);
for(int i=1;i<=m;i++){
int u,v;
read(u),read(v);
add_edge(u,v);
add_edge(v,u);
}
for(int i=1;i<=n;i++){
if(fa[i]==0){
init_dfs(i);
}
}
for(int i=1;i<=n;i++){
if(sum[i]>1&&(start==0||dep[i]<dep[start])){
start=i;
}
}
if(start==0){
puts("NO");
return 0;
}
work_dfs(start);
start=fa[start];
int u=edge[1].u,v=edge[2].u;
while(u!=v){
if(dep[u]>dep[v]){
u=fa[u];
}
else{
v=fa[v];
}
}
bottom=u;
calc_path(start,bottom,ans[0]);
calc_path(start,edge[1].v,ans[1]);
calc_path(edge[1].u,bottom,ans[1]);
calc_path(start,edge[2].v,ans[2]);
calc_path(edge[2].u,bottom,ans[2]);
puts("YES");
for(int i=0;i<3;i++){
printf("%u ",ans[i].size());
for(int j=0;j<(int)ans[i].size();j++){
printf("%d ",ans[i][j]);
}
puts("");
}
return 0;
}