[CF]Cycling City

题目大意：给定一张无向图，问图中是否存在两个点，使得这两个点之间有三条路径，而且三条路径没有公共点。

解法：

我们可以先走出来一个环，再出环上任意一点走到另外一点。就像这样：

aaarticlea/png;base64,iVBORw0KGgoAAAANSUhEUgAAArsAAAGCCAIAAABvnJwtAAAAAXNSR0IArs4c6QAAAARnQU1BAACxjwv8YQUAAAAJcEhZcwAADsMAAA7DAcdvqGQAABfJSURBVHhe7dvbgfPIcYBRx+WAnIneHYYjcDIORpZGH/SDS2JAzvDSDZzzpq4CyWFd2Fqt/uPvAAB73BgAgH1uDADAPjcGAGCfGwMAsM+NAQDY58YAAOxzYwAA9rkxAAD73BgAgH1uDADAPjcGAGCfGwMAsM+NAQDY58YAAOxzYwAA9rkxAAD73BgAgH1uDADAPjcGAGCfGwMAsM+NAQDY58YAAOxzYwAA9rkxAAD73BgAgH1uDADAPjcGAGCfGwMAsM+NAU7hP16stwGOy5zD3PrFnkQfGpiQAYYJ9Ht7aP2pwKhMKYyl30++9KUAAzCQ8GH9NnKHvjLgE0wgvFU/fe/Ve79Yb/ZevTfweuYNXqtftpfpbSbRh36Z3gZ4AQMGz9fP1/P0uofWn/pUvTTwDCYKnqPfqGfoFU+vr+MZekXgFwwS/Fw/R7/Ta3GHvrLf6bWABxkeeEw/O7/QC/FrfaG/0AsBdzAwsK+flx/pJXiLvvQf6SWADYYENvVL8rie56MqxuN6HrhkNuCv+t14UA8zpIr0oB4GvhgJSL8SD+phJlHZHtTDcG4mgbPrN+ERPcnkKucjehJOyQBwUv0C3K3HOKjKfLcegzPR95xOK/8+PcNpVPi79RicgHbnLFrw9+kZTqxWuE/PwKFpdA6ujX6fnoGVmuM+PQNHpL85rFb4HXoAvlW73KEH4Fh0NgfU2t5TNjyoBtpTNhyFnuZQWtXfKhV+rZbaUzZMTitP5n/+53/+9re/9R9YtJj3lA1PVXvtKRumpYkn84/rgtWz9q9d/L1S4cVquG+VChPSvsyqBfytUuGNar5vlQpT0bhMpo27p2z4kBpxT9kwA/3KTNqy3yoVxlBfbisPhqdZmUPLdVt5MKTadFt5MDBtyuhaqNvKg+HVstvKgyFpUMbVEt1WHkyl9t1WHgxGazKiFue28mBatfK28mAYmpKxtCy3lQeHUFtvKw8GoB0ZRQtyW3lwOLX4tvLgozQiQ2gvbigJDq1231YefIgW5MPahRtKgtOo9TeUBJ+g//iYVuCGkuCUGoMNJcF76Tw+o823oSQ4t+bhljLgjbQd79bC21AS8KXB2FASvIWG463ac7eUAVxpSG4pA15Pt/EmrbdbygC+1cDcUga8kj7jHdpqt5QB3KGxuaUMeBlNxmu1zG4pA3hQI3RLGfAC2osXaofdUgbwIw3SLWXAs+ktXqLVdUsZwK81VLeUAc+jq3i+NtYtZQBP0mjdUgY8iZbiydpVVwoDL9CY3VIG/Jpm4mnaT7eUAbxMw3ZLGfA7OonnaDNdKQy8RYN3pTD8gjbiCdpJVwoDb9T4XSkMP6WH+JVW0S1lAJ/QHF4pDI/TPfxcG+hKYeCjGsgrheFBWocfavdcKQwMoLG8UhgeoW/4ibbOlcLAMBrOK4XhbpqGx7RsrhQGhtSgXikMd9AuPKAdc6UwMLDG9Uph2KNXuFfb5UphYHgN7ZXC8C2Nwl3aK1cKA5NodK8Uhm26hH1tlEvFgAk1xpeKwQYtwo52yaViwLQa5kvF4Bb9wXfaIpeKAZNrpC8Vgyuag03tj0vFgENosK8UhhVtwW2tjUvFgANpvK8UhoWe4IYWxqViwOE05FcKwxcNwV+1Ki4VAw6qUb9SGNwY+IuWxKViwKE18FcKc3pagT9aD5eKASfQ2F8pzLnpA9JiuFQMOI2G/0phTkwT8E+thEvFgJNpBVwqxolpAmwH4K9aBJeKcVY64OzaBJeKASfWOrhUjFNS/lNrB1wqBpxeS+FSMc5H7c+r6b9UDOBLq+FSMU5G4U+qub9UDGClBXGpGGei6mfUxF8qBnClNXGpGKeh5GfUuK8UANjQslgpwGko+ek06ysFAL7VylgpwDmo97k05SsFAO7Q4lgpwAko9ok035eKAdyn3bFSgKNT6bNosi8VA7hb6+NSMQ5Nmc+isV4pAPCglshKAQ5NmU+hmV4pAPAjrZKVAhyXGh9f07xSAOAXWigrBTgoBT6+RnmlAMAvtFAuFeOIVPfgGuKVAgC/1lpZKcARqe6RNcErBQCepOWyUoDDUdrDanYvFQN4nvbLSgGORV0Pq8FdKQDwVK2YlQIci7oeU1O7UgDgBVo0KwU4EEU9oOZ1pQDAy7RuVgpwFCp6QA3rSgGAl2ndrBTgKFT0aJrUlQIAL9bSWSnAISjn0TSmi04B3qLVs+iUQ1DOQ2lGVwoAvEWrZ6UA81PL42g6VwoAvFELaKUAk1PI42g0VwoAvFELaKUAk1PIg2guVwoAvF1raKUAM1PFg2goF50CfEjLaNEpM1PFI2giVwoAfEjLaKUA01LCI2gcF50CfFQradEp01LC6TWLKwXgKOrsu/UYn1Y9VgowJ/WbXoO46BQmUeN+SB+Cl+mLXnTKnNRvbk3hSgEYTA06iT40v9YXulKACSne3BrBRafwaXXksfS38aC+vkWnTEjxJtb8rRSAt6sFz6S/nD19XysFmI3KTazhW3QK71LnvVLv9Lief5felQ19TYtOmY3KzarJWykAr1S3PU+v+yF9iGfr1Vn0vawUYCrKNqvGbtEpvEBN9ju91gz6xE/Si55eX8eiU6aibFNq5lYKwPPUWz/VqxxFf9Uv9EJn1bewUoB5qNmUGrhFp/AMddWDevg0+rN/qlc5mf74RafMQ82m1MAtOoVfqJke0ZP84gLR8+fQ37zolHmo2XyatpUC8Lh66BE9yYa+psf1/HH1d64UYBIKNp9GbdEpPKLuuVuP8aC+vgf18BH1Fy46ZRIKNpnmbKUA3KGmuU/P8CR9rY/oyQPpD1spwAxUazIN2aJT2FPH3KEHeJm+6Ef05CH0Jy06ZQaqNZmGbNEpbKhR7tMzvFFf/X16ZnL9MYtOmYFqzaQJWykAV2qRO/QAH1Ux7tMzc+pvWCnA8JRqJo3XolO4VH/sKZvBVJ779Mxs+vSLThmeUs2k8Vp0Cl9qiz1lM7wKdocemEefe9Epw1OqaTRbKwU4vRpiT9nMpvrdoQeG18ddKcDY1GkaDdaiU86tbvhWqcyviu4pe2x91kWnjE2dptFgLTrlrOqDb5XKsVTdO/TAkPqIi04ZmzrNoalaKcD51AHfKpVDq9h7yh5MH26lAANTpDk0UotOOZnK/61SOY0Kf4ceGEYfa9EpA1OkOTRSi045jQq/rTxOrFbYU/YA+kCLThmYIs2hkVp0yglU8m3lwZfaYk/ZH9VHWXTKwBRpAs3TSgEOrWJvKw9uqUu+VeqH9CFWCjAqFZpAw7TolOOq0tvKgz11zLdK/YQ+waJTRqVCE2iYFp1yRNV4W3nwoBroW6W+UW+86JRRqdAEGqZFpxxL1d1WHvxCzfStUt+it1x0yqhUaHRN0koBjqK6bisPnqTG+lapr9f7LTplSMozusZo0SlHUV03lAQvUJN9q9RX6p0WnTIk5RldY7TolPlV0Q0lwYvVcN8q9TV6j0WnDEl5RtcYLTplZtVyQ0nwRjXft0p9tl590SlDUp7RNUaLTplTVdxQEnxIjfitUp+n1110ypCUZ3SN0aJTZlP9tpUHA6gpt5X3DL3iolOGpDxDa4YWnTKb6rehJBhMDbqtvF/r5RadMh61GVoDtOiUeVS5DSXBwGrWbeX9Qi+06JTxqM3QGqBFp8ygmm0oCSZR424o6ad6lUWnjEdthtYALTplbFVrQ0kwoZp4Q0mP6/lFp4xHbYbWAC06ZVTVaVt5MK1aeVt5j+jJRaeMR22G1gAtOmVIFWlDSXAItfW28u7TM4tOGY/aDK0BWnTKYCrPhpLgcGrxbeXtKXvRKeNRm3E1PSsFGEaF2VASHFrtvqGkb5W66JTxqM24mp5Fp4yhqmwoCU6j1t9Q0rbyFp0yGIUZV6Oz6JQBVJINJcH5NAMbSrqljEWnDEZhxtXoLDrloyrGhpLg3JqHDSVdKrbolMEozLganUWnfEhl2FAS8KXB2FDSSoFFpwxGYcbV6Cw65e0qwIaSgCsNyYaSvnS06JTBKMy4Gp1Fp7xRX/228oBtTcuGmzn/OmQ0CjOuRmfRKe/S976hJOA+Tc59eobBKMy4Gp1Fp7xe3/iGkoAHNUJ36AEGozDjanQWnfJKfdcbSgJ+oXH6VqkMRmHG1egsOuU1+pa3lQc8Q3O1oSQGozDjanQWnfJsfb/bygOerRm7UpjBKMy4Gp1FpzxP3+y28oCXadguFWMwCjOuRudSMX6nb3NbecBbNHiLThmMwoyr0blSmB/pS9xWHvBGjd+iUwajMONqdDaUxN364raVB7xdQ7jolMGcvjD/99//WYsu/vO//6/Yh/V5vlUq3+rL2lYe8CGN4qJTBnPmwvzvf9Wc1/7rf8v5pD7LHXqAK31B28oDPqqBXHTKYE5bmD//bOGvt4N/XiQmuzH8S4/xpS9lW3nAABrLRacM5qyF6Z8vDPO/QNzy9Qn/uHl47V9pZ9YXsa08YBgN56JTBnPSwiz/hGGIf5bwja8P+UenfhRv6S//VqnAYBrRRacM5qyFmeGfMfzD14f8o9NFp98q9dD6U79VKjCepnTRKeM5a222/zWGofQZF51eKvatUo+lv21P2cComtVFp4znvLW5+L9Vjnpt6OMtOr2ljD1lz6y/5A49AIytiV10ynjOXZu//P8rx7s39MEWnW4r7w49MI8+9316BphBc7volPGozdDXhj7TotM9Zd+nZ0bVp7xPzwBTaYAXnTIetcmY/yNFn2fR6d167D49M4A+0CN6EphQY7zodNdf/tvehqH/VbXZWLVrw/37kH2aRacP6uEH9fC79K4P6mFgZs3zotNdbgxvZ+f+xdKDR/nHDGu9xE/1Ks/QK/5UrwLMr6leKfCo/hvf6P+f+alZvn/VleGIN4Z/67Ve4KWv/68XB46k8V50+gNuDK930i38j9bauBJ0YRin6b4+zh+dPkkvOrA+KHBQjfqi0x9wY3i9894YvprzL721HI/Uc//6QP/W6Qv0BmPoMwFH18wvOv0BN4bXO+1q/vfl4Iah/k2ZPtOi09fr/d6ldwVOphWw6PQH3Bhe7+Sb+q//ru2AvdYnWynwXr33k/SiwOm1FBad/oAbw+vZ3RP4mqM/OgWYXEtt0enPuDG8np+fCXyN0h+dAkyupbbo9GfcGF7Pz88Evkbpj04BJtdSW3T6M24Mr+fnZwJfo3ShAMDM2miLTn/GjeH1/PbM4Wua/ugUYFqts0WnP+bG8Hp+e+bwNVB/dAowrdbZotMfc2N4Pb89c/gaqD86BZhW62zR6Y+5Mbye3545fA3UhQIAE2qRrRT4MTeG1/PDM42vmfqjU4AJtcgWnf6GG8Pr+eGZxtdY/dEpwIRaZItOf8ON4fX88Ezja6wuFACYSitspQBjU6eZNFuLTgGm0gpbdMrwlGomjdeiU4CptMIWnTI8pZpJ47VSAGASLa+VAgxPqSbThC06BZhEy2vRKTNQrck0ZItOASbR8lp0ygxUazIN2UoBgOG1tlYKMAPVmk9ztugUYHitrUWnTELB5tOorRQAGFs7a9Epk1Cw+TRqKwUABtbCWinAJBRsSk3bolOAgbWwFp0yDzWbUgO3UgBgSK2qlQLMQ81m1cwtOgUYUqtq0SlTUbZZNXYrBQAG05JaKcBUlG1iTd6iU4DBtKQWnTIblZtYw7dSAGAYraeVAsxG5ebW/C06BRhG62mlALNRubk1fysFAAbQYlopwIQUb26N4EoBgAG0mFYKMCHFm15TuFIA4KNaSSsFmJP6HUGzuOgU4KNaSSsFmJP6HUGzuFIA4ENaRisFmJYSHkQTuegU4ENaRotOmZkqHkRDuVIA4O1aQysFmJkqHkdzuVIA4L3aQYtOmZxCHkejuVIA4I1aQCsFmJxCHkrTuVIA4C1aPSsFmJ9aHk0zuugU4C1aPSsFmJ9aHk0zulIA4MVaOisFOATlPKAmdaUAwMu0blYKcBQqekAN60oBgJdp3awU4ChU9Jia15UCAC/QolkpwIEo6mE1tSsFAJ6qFbNSgGNR18NqcFcKADxVK2alAMeirkfW7K4UAHiSlstKAQ5HaQ+uCV4pAPBrrZWVAhyR6h5cQ3ypGMDvtFNWCnBEqnt8zfFKAYBfaKGsFOCgFPgUmuaVAgA/0ipZKcBxqfFZNNMrBQAe1BK5VIzjUuOzaKYvFQO4W+vjUjEOTZlPpMm+VAzgPu2OlQIcnUqfS/O9UgDgDi2OlQKcgGKfTlO+UgDgW62MlQKcg3qfUbO+UgBgQ8viUjHOQb3PqFm/VAzgSmviUjFOQ8lPqom/VAxgpQVxqRhnourn1dxfKgbwpdVwqRgno/Cn1vRfKgacXkvhUjHOR+3Prh1wqRhwbm2ElQKckvLj0gDc0C5YKcBZ6QD+qX1wqRhwPm2BlQKcmCbgn1oJl4oBJ9MKuFSME9MEpK1wqRhwGg3/pWKcmz7gj3bDpWLACTT2l4pxelqBC22IS8WAQ2vgLxUDNwautSeuFAYOpyG/Uhi+aAhuaFtcKQwcSON9pTAs9AS3tTOuFAYOocG+UhhWtAXfaXlcKgZMrpG+Uhgu6Qx2tEIuFQOm1TBfKga36A/2tUsuFQMm1BhfKgYbtAh3aaNcKgZMpQG+VAy26RLu1V65UhgYXkN7pTB8S6PwgLbLlcLAwBrXK4Vhj17hMe2YK4WBITWoVwrDHbQLP9GyuVIYGEnzeaUw3EfH8EOtnCuFgQE0llcKwyP0DT/X7rlSGPioBvJKYXiQ1uFX2kBXCgMf0iheKQyP0z08QavoSmHgjRq/K4Xhp/QQz9FOulIYeIsG70ph+AVtxNO0ma4UBl6skbtSGH5HJ/FM7adbygBeoDG7pQz4Nc3E87WobikDeJ6m60pheBItxUu0sW4pA/i1huqWMuB5dBWv0t7aUBLwIw3ShpLgqTQWr9UCu6UM4EGN0C1lwAtoL96hZXZLGcAdGpsNJcFr6DDepJV2SxnAtxqYW8qAV9JnvFXr7ZYygCsNyS1lwOvpNt6tPbehJGDRbNxSBryFhuMzWni3lAGn10jcUga8kbbjY9p8G0qCU2oMNpQE76Xz+LBW4IaS4DRq/Q0lwSfoPz6vXbitPDi02n1befAhWpBRtBS3lQeHU4tvKw8+SiMylhbktvLgEGrrbeXBALQjI2pZbigJZlY3bysPhqEpGVeLc0NJMKGaeENJMBityehaotvKg+HVstvKgyFpUObQQt1WHgypNt1WHgxMmzKNNuu3SoVh1JrfKhXGplOZTCv2W6XC59SLe8qGGehXptS63VM2vFHNt6dsmIeuZW5t32+VCi9Ww32rVJiQ9uUIWsbfKhVeoCb7VqkwLU3McbSY95QNv1ZL7SkbJqeVOaD29J6y4UE10J6y4Sj0NIfV2r5DD8C3apc79AAci87m4Frh9+kZWKk57tMzcET6m1Nond+txzixWuFuPQbHpcs5l7b73XqM06jwd+sxOAHtzkm17+/WYxxUZb5bj8GZ6HvOrl+AR/Qk86uid+sxOCUDAOk34RE9yVQq3iN6Es7NJMBf9SvxoB5mSBXpQT0MfDESsKnfjcf1PB9VMR7X88AlswH7+iX5kV6Ct+hL/5FeAthgSOAx/bz8Qi/EM/Sd/lSvAtzBwMDP9bPzO70Wd+gr+51eC3iQ4YHn6Ofo13o5vvSl/FovB/yCQYIn6zfqqXrpQ+tPfapeGngGEwWv1W/Xa/QeU+mjv0bvAbyAAYO36pftvXrvF+vN3qv3Bl7PvMEn9bvH3frigLczfjCWfhj50pcCDMBAwgT6/Ty0/lRgVKYUJtaP7VT66MBsTC8cX7/Vr9Q7AcdlzgGAfW4MAMA+NwYAYJ8bAwCwz40BANjnxgAA7HNjAAD2uTEAAPvcGACAfW4MAMA+NwYAYJ8bAwCwz40BANjnxgAA7HNjAAD2uTEAAPvcGACAfW4MAMA+NwYAYJ8bAwCwz40BANjnxgAA7HNjAAD2uTEAAPvcGACAfW4MAMA+NwYAYJ8bAwCwz40BANjnxgAA7HNjAAD2uTEAAPvcGACAfW4MAMA+NwYAYJ8bAwCwz40BANjnxgAA7HNjAAD2uTEAAPvcGACAfW4MAMA+NwYAYJ8bAwCwz40BANjnxgAA7HNjAAD2uTEAAPvcGACAfW4MAMCev//9/wHI9AiXPKDorQAAAABJRU5ErkJgggA=" alt="" width="439" height="242" />

这种图有什么性质？有环。

这是什么图我们可能不知道，但是我们知道这不是什么图啊！这张图一定不是仙人掌！

然后就是如何判断仙人掌和如何输出答案的问题了

参考了这个大佬的博客，我们了解到，可以利用返祖边来判断仙人掌

显然仙人掌中的一条边不能同时出现两个环内

正如大佬所说的“如果一条树边被两条或者以上的返祖边覆盖，那么图就肯定不是一个仙人掌”

我们建出DFS树，可以发现，第一条返祖边能确定一个环，而第二条返祖边能确定三条路径的起点和终点

设起点深度小，终点深度大，我们可以发现终点是两个返祖边中深度最大的两个点的LCA

而起点则是第二条返祖边上深度最大的点与DFS树上一点相连接的一点

然后再xjbDFS一下输出路径即可代码：

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #define M 200010

 using namespace std;

 struct point{

     int to,next;

 }e[M<<];

 int n,m,num,top,l1,l2,r1,r2,S,T;

 int ans[M],head[M],deep[M],f[M];

 int fa[M][];

 bool vis[M];

 void add(int from,int to)

 {

     e[++num].next=head[from];

     e[num].to=to;

     head[from]=num;

 }

 void dfs(int x)

 {

     vis[x]=true;

     for(int i=head[x];i;i=e[i].next)

     {

         int to=e[i].to;

         if(to==fa[x][]) continue;

         if(!vis[to])

         {

             deep[to]=deep[x]+;

             fa[to][]=x;

             dfs(to);

         }

         else if(deep[to]<deep[x])//返祖

         {

             f[to]--;

             f[x]++;

         }

     }

     f[fa[x][]]+=f[x];

 }

 void DFS(int x)

 {

     for(int i=head[x];i;i=e[i].next)

     {

         int to=e[i].to;

         if(to==fa[x][]) continue;

         if(deep[to]==deep[x]+)

         {

             DFS(to);

             if(l2) return;

         }

         else if(deep[to]<deep[S])//找到两条返祖边

         {

             if(l1) r2=x,l2=to;

             else r1=x,l1=to;

             if(l2) return;

         }

     }

 }

 int lca(int x,int y)

 {

     if(deep[x]<deep[y]) swap(x,y);

     for(int i=;i>=;i--)

         if(deep[fa[x][i]]>=deep[y])

             x=fa[x][i];

     if(x==y) return y;

     for(int i=;i>=;i--)

         if(fa[x][i]!=fa[y][i])

         {

             x=fa[x][i];

             y=fa[y][i];

         }

     return fa[x][];

 }

 int main()

 {

     scanf("%d%d",&n,&m);

     for(int i=;i<=m;i++)

     {

         int x,y; scanf("%d%d",&x,&y);

         add(x,y); add(y,x);

     }

     for(int i=;i<=n;i++)

         if(!vis[i])

             dfs(i);

     for(int i=;i<=n;i++)

         if(f[i]>)

         {

             S=i;

             break;

         }

     if(S==) {printf("NO"); return ;}

     printf("YES\n");

     DFS(S);

     for(int j=;j<=;j++)

         for(int i=;i<=n;i++)

             fa[i][j]=fa[fa[i][j-]][j-];

     T=lca(r1,r2);

     if(deep[l1]<deep[l2]) swap(l1,l2),swap(r1,r2);

     S=l1;

     int now=T;

     top=;

     while()

     {

         ans[++top]=now;

         if(now==S) break;

         now=fa[now][];

     }

     printf("%d ",top);

     for(int i=top;i>=;i--) printf("%d ",ans[i]);

     printf("\n");

     top=;

     ans[++top]=S;

     now=r1;

     while()

     {

         ans[++top]=now;

         if(now==T) break;

         now=fa[now][];

     }

     printf("%d ",top);

     for(int i=;i<=top;i++) printf("%d ",ans[i]);

     printf("\n");

     top=;

     if(S==l2)

     {

         ans[++top]=S;

         now=r2;

         while()

         {

             ans[++top]=now;

             if(now==T) break;

             now=fa[now][];

         }

     }

     else

     {

         now=S;

         while()

         {

             ans[++top]=now;

             if(now==l2) break;

             now=fa[now][];

         }

         now=r2;

         while()

         {

             ans[++top]=now;

             if(now==T) break;

             now=fa[now][];

         }

     }

     printf("%d ",top);

     for(int i=;i<=top;i++) printf("%d ",ans[i]);

     return ;

 }