一道难得恰到好处的构造题。
分析
因为要构造三条从 \(s\) 到 \(t\) 的路径，且三条路径中任意两条路径经过的点集的交集等于 \(\{s,t\}\)。我们知道当两条路径经过的点集的交集等于 \(\{s,t\}\) 时，这两条路径将会构成一个环。因此题意转化为要求我们找到两个经过的边集有重合的环。看似这步转化是将题目变复杂了，其实还是变简单了。将图画出来，大致长成下图的样子。
两个环分别是 \(s\rightarrow a\rightarrow t\) 和 \(s\rightarrow b\rightarrow c\rightarrow t\)。可以发现，如果建出 dfs 树，那么所有的非树边都将是返祖边，那么我们只需要统计每条边被哪条边所覆盖，当其被第二次覆盖时，这两条边就是我们要找的 \((a,t)\) 和 \((b,c)\) 了。可以发现，找边的覆盖并不需要用到非树边为返祖边的性质，所以任意生成一棵生成树均可实现以上的操作。；
这里再介绍另一种做法。对于找环这个事情，我们首先想到的是 tarjan 找点双。那么同时找两个边集有交环同理也是可以用 tarjan 找的。回到上图，我们要找的其实是 \((a,t)\) 和 \((b,c)\) 两条边。令 \(low_u\) 表示以 \(u\) 为起点，经过至多一条返祖边能到达的最小 dfs 序，在哪个点走的这条返祖边显然也是可以在 tarjan 中得到的。令 \(nxt_u\) 表示以 \(u\) 为起点，经过至多一条返祖边能到达的次小 dfs 序（不必严格次小），也能找到从哪个点走的返祖边。可以发现从起点 \(s\) 开始，经过一条返祖边，到达的 \(t\) 点和 \(c\) 点的 dfs 序均小于 \(s\)。于是我们找到了有解的情况，存在一个点 \(s\) 使得 \(low_s<dfn_s\) 且 \(nxt_s<dfn_s\)。这两个地方都不带等号，因为如果带了等号就会出现两个环上的点有交集，边却没有交集的情况，这是不符合要求的。
可以发现上面的分析中，至多一条是被标粗的。强调至多一条，一是 tarjan 本身是这么要求的，还有就是如果不要求至多一条，就会出现下图环套环的情况。
这种时候，如果不要求经过至多一条返祖边，则会出现终点选到 \(c\)的情况，因为 \(t\) 不能选两次，导致只会有两条合法的路径。实际上我们要求经过至多一条返祖边，终点会选到 \(t\)，这样就有三条合法的路径。
Code
这里给出第二种用 tarjan 的做法的代码。
点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pii pair<int,int>
#define pdi pair<double,int>
#define pb push_back
#define eps 1e-9
#define mp make_pair
using namespace std;
namespace IO{
template<typename T>
inline void read(T &x){
x=0;
int f=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
x=(f==1?x:-x);
}
template<typename T>
inline void write(T x){
if(x<0){
putchar('-');
x=-x;
}
if(x>=10){
write(x/10);
}
putchar(x%10+'0');
}
template<typename T>
inline void write_endl(T x){
write(x);
putchar('\n');
}
template<typename T>
inline void write_space(T x){
write(x);
putchar(' ');
}
}
using namespace IO;
const int N=2e5+10,inf=1e9;
int n,m,dfn[N],rdfn[N],fa[N],idx;
pii low[N],nxt[N];
vector<int>e[N];
deque<int>ans;
void tarjan(int u,int father){
fa[u]=father;
dfn[u]=++idx;
rdfn[idx]=u;
low[u]=mp(idx,u),nxt[u]=mp(inf,0);
for(auto v:e[u]){
if(!dfn[v]){
tarjan(v,u);
if(low[v]<low[u]){
swap(low[u],low[v]);
}
if(low[v]<nxt[u]){
swap(nxt[u],low[v]);
}
}
else if(v!=fa[u]){
pii tmp=mp(dfn[v],u);
if(tmp<low[u]){
swap(low[u],tmp);
}
if(tmp<nxt[u]){
swap(nxt[u],tmp);
}
}
}
if(low[u].first<dfn[u]&&nxt[u].first<dfn[u]){
puts("YES");
int ed=rdfn[nxt[u].first],now=u;
while(now!=ed){
ans.pb(now);
now=fa[now];
}
ans.pb(ed);
write_space(ans.size());
while(ans.size()){
write_space(ans.front());
ans.pop_front();
}
putchar('\n');
now=nxt[u].second;
while(now!=u){
ans.push_front(now);
now=fa[now];
}
ans.push_front(u);
ans.pb(ed);
write_space(ans.size());
while(ans.size()){
write_space(ans.front());
ans.pop_front();
}
putchar('\n');
now=ed;
while(now!=rdfn[low[u].first]){
ans.push_front(now);
now=fa[now];
}
ans.push_front(rdfn[low[u].first]);
now=low[u].second;
while(now!=u){
ans.push_front(now);
now=fa[now];
}
ans.push_front(u);
write_space(ans.size());
while(ans.size()){
write_space(ans.front());
ans.pop_front();
}
exit(0);
}
}
void solve(){
read(n),read(m);
for(int i=1;i<=m;i++){
int u,v;
read(u),read(v);
e[u].pb(v);
e[v].pb(u);
}
for(int i=1;i<=n;i++){
if(!dfn[i]){
tarjan(i,0);
}
}
puts("NO");
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
int t=1;
while(t--){
solve();
}
return 0;
}