CSES - Shared codeLink to this code: https://cses.fi/paste/572b9372c783fef2695128/
#include<iostream>
#include<algorithm>
#include<vector>
#include<set>
using namespace std;
vector<int>solution;
int node;
void dfs(set<int>*graph,int u){
while(!graph[u].empty()){
node=*graph[u].begin();
graph[u].erase(node);
graph[node].erase(u);
dfs(graph,node);
}
solution.emplace_back(u);
}
inline void im(){
cout<<"IMPOSSIBLE";
}
int main(){
int n,m,a,b,cntEven=0,len;
cin>>n>>m;
len=m;
vector<int>deg(n+1,0);
set<int>graph[n+1];
while(m--){
cin>>a>>b;
deg[a]++;
deg[b]++;
graph[a].insert(b);
graph[b].insert(a);
}
int start=1;
for(int i=1;i<=n;i++){
cntEven+=deg[i]%2==0;
if(deg[i]&1){
start=i;
}
}
if(cntEven!=n and cntEven!=n-2){
im();
return 0;
}
dfs(graph,start);
if(solution.size()!=(len+1)){
im();
return 0;
}
if(solution[0]!=1 or solution.back()!=1){
im();
return 0;
}
for(int i:solution)cout<<i<<" ";
return 0;
}