CSES - Shared codeLink to this code:
https://cses.fi/paste/ca493204aa672b9f3c7aa2/
/*
No Matter How many times I fall,
I have to be 1900+ This Year
*/
/****Bismillahir rahmanir rahim****/
//#include<bits/stdc++.h>
#ifndef _GLIBCXX_NO_ASSERT
//#include <cassert>
#endif
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <cwchar>
#include <cwctype>
#if __cplusplus >= 201103L
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
//#include <cstdalign>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
//#include <cuchar>
#endif
// C++
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#if __cplusplus >= 201103L
#include <array>
#include <atomic>
#include <chrono>
#include <codecvt>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#endif
#if __cplusplus >= 201402L
#include <shared_mutex>
#endif
#if __cplusplus >= 201703L
#include <any>
//#include <charconv>
// #include <execution>
//#include <filesystem>
#include <optional>
//#include <memory_resource>
#include <string_view>
#include <variant>
#endif
#if __cplusplus > 201703L
#include <bit>
// #include <compare>
// #include <span>
// #include <syncstream>
#include <version>
#endif
using namespace std;
/*#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef tree<long long, null_type, less<long long>, rb_tree_tag,
tree_order_statistics_node_update>
is;*/
#define fb find_by_order
#define ok order_of_key
#define mem(x,y) memset(x,y,sizeof x)
typedef long long ll;
typedef int ii;
typedef pair<ll,ll> pi;
typedef vector<pair<ll,ll>> vii;
#define map unordered_map
#define INF 1000000000000000007
#define pi1 3.141592654
#define boost() reserve(1024)
#define fast() max_load_factor(0.25)
#define T while(t--)
#define for2(i,a,b) for(i=a;i>=b;i--)
#define for3(i,a,b) for(i=a;i<=b;i=i+2)
#define for1(i,a,b) for(i=a;i<=b;i=i+1)
#define for4(i,a,b) for(i=a;i>=b;i=i-2)
#define pb push_back
#define pf push_front
#define mp make_pair
#define ff first
#define ss second
#define si set<ll>
#define se multiset<ll>
typedef long double ld;
typedef vector<ll> vi;
#define all(v) sort(v.begin(),v.end())
#define all1(v) sort(v.rbegin(),v.rend())
#define sorted(v) is_sorted(v.begin(),v.end())
#define sorted1(v) is_sorted(v.begin(),v.end())
#define pff(uuv) printf("%lld\n",uuv)
#define pf1(uu) printf("%.20Lf\n",uu)
bool comp(pair<ll,ll> aa, pair<ll,ll> bb) {
if (aa.ff != bb.ff) return aa.ff > bb.ff;
return aa.ss < bb.ss;
}
bool comp1(pair<ll,ll> aa, pair<ll,ll> bb) {
if (aa.ff != bb.ff) return aa.ff < bb.ff;
return aa.ss > bb.ss;
}
bool comp2(pair<ll,ll> aa, pair<ll,ll> bb) {
if (aa.ff != bb.ff) return aa.ff > bb.ff;
return aa.ss < bb.ss;
}
bool comp3(pair<ll,ll> aa, pair<ll,ll> bb) {
if (aa.ff != bb.ff) return aa.ff < bb.ff;
return aa.ss > bb.ss;
}
ll rup(ll ik,ll ikk){
if(ik%ikk==0) return ik/ikk;
else return (ik/ikk)+1;
}
ll gcd(ll a,ll b){
if(b==0) return a;
return gcd(b,a%b);
}
ll lcm(ll a ,ll b){
return (a*b)/gcd(a,b);
}
ll nm(ll a,ll b){
return (b + (a%b)) % b;
}
struct hp {
template <class T1, class T2>
size_t operator()(const pair<T1, T2>& p) const
{
auto hash1 = hash<T1>{}(p.first);
auto hash2 = hash<T2>{}(p.second);
return hash1 ^ hash2;
}
};
/*ll parent[1000005];
void makeset(ll i){
parent[i]=i;
}
ll find(ll u){
if(parent[u]==u) return u;
return parent[u]=find(parent[u]);
}
void uni(ll xx,ll yy){
ll a=find(xx);
ll b=find(yy);
if(a!=b){
parent[a]=b;
}
}*/
/*ll sieve[1100]={};
void sieve1(ll n1){
for (ll x1 = 2; x1 <= n1; x1++) {
if (sieve[x1]) continue;
for (ll u1 = 2*x1; u1 <= n1; u1 += x1) {
sieve[u1] = x1;
}
}
}*/
/*std::ostream& operator << (std::ostream& dest, __int128_t value) {
std::ostream::sentry s(dest);
if (s) {
__uint128_t tmp = value<0?-value:value;
char buffer[128];
char* d = std::end(buffer);
do {
-- d;
*d = "0123456789"[tmp%10];
tmp/=10;
}while(tmp!=0);
if(value<0) {
--d;
*d = '-';
}
ll len = std::end(buffer)-d;
if (dest.rdbuf()->sputn(d,len)!=len) {
dest.setstate(std::ios_base::badbit);
}
}
return dest;
}*/
ll modpow(ll x1, ll n1, ll m1) {
if (n1 == 0) return 1%m1;
long long u1 = modpow(x1,n1/2,m1);
u1 = (u1*u1)%m1;
if (n1%2 == 1) u1 = (u1*x1)%m1;
return u1;
}
ll n,m;
vi adj[100002];
bool visited[100002];
ll yo[100002];
vii v2;
void dfs(ll s,ll e){
if(visited[s]){
//cout<<e<<" "<<s<<"\n";
v2.pb({e,s});
//aa=e;
//bb=s;
return;
}
//cout<<s<<" "<<e<<"\n";
yo[s]=e;
visited[s]=true;
for(auto u : adj[s]){
if(u==e) continue;
//cout<<u<<" "<<s<<"\n";
dfs(u,s);
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
ll t=1;
// cin>>t;
while(t--){
cin>>n>>m;
ll x,y;
for(ll i=1;i<=m;i++){
cin>>x>>y;
adj[x].pb(y);
adj[y].pb(x);
}
for(ll i=1;i<=n;i++){
if(!visited[i]) dfs(i,-1);
}
if(v2.size()==0){
cout<<"IMPOSSIBLE\n";
continue;
}
ll aa=v2[0].ff;
ll bb=v2[0].ss;
//cout<<aa<<" "<<bb<<"\n";
//cout<<yo[1]<<"\n";
vi ans;
while(true){
ans.pb(aa);
if(bb==aa) break;
aa=yo[aa];
}
ans.pb(ans[0]);
cout<<ans.size()<<"\n";
for(auto u : ans) cout<<u<<" ";
cout<<"\n";
}
}