CSES - Shared codeLink to this code:
https://cses.fi/paste/801370f1f83b034f66ccd0/
#include<bits/stdc++.h>
using namespace std;
class RoundTrip{
int n,m;
vector<int> *g;
int start,end;
public:
vector<int>p;
RoundTrip(int n,int m,vector<int> g[]){
this->n=n;
this->m=m;
this->g=g;
p.resize(n+1,0);
start=end=-1;
}
bool dfs(int u,int parent){
for(int v:g[u]){
if(v!=parent){
if(p[v]==0){
p[v]=u;
if(dfs(v,u))return true;
}else{
start=u;
end=v;
return true;
}
}
}
return false;
}
void printLoop(){
if(start==-1){
cout<<"IMPOSSIBLE\n";
return;
}
vector<int>ans(1,end);
while(start!=end){
ans.push_back(start);
start=p[start];
}
ans.push_back(start);
cout<<ans.size()<<endl;
for(auto i:ans)cout<<i<<" ";
}
};
int main(){
int n,m,a,b;
cin>>n>>m;
vector<int>g[n+1];
for(int i=0;i<m;i++){
cin>>a>>b;
g[a].push_back(b);
g[b].push_back(a);
}
RoundTrip ans(n,m,g);
for(int i=n;i>=1;i--){
if(ans.p[i])continue;
if(ans.dfs(i,-1))break;
}
ans.printLoop();
return 0;
}