Shared code

#pragma GCC optimize("O3")
#pragma GCC target("avx2")
#pragma GCC optimize("unroll-loops")
 
#include<bits/stdc++.h>
using namespace std;
 
typedef long double ld;
typedef long long int ll;
typedef pair<int, int> pi;
typedef pair<long long, long long> pll;
 
#define ff first
#define ss second
#define pb push_back
#define int long long   // Make sure to use ll everywhere while commenting this, to avoid overflow
#define sz(v) (int)v.size()
#define inf 2147483647
#define llinf 9223372036854775807
#define all(v) v.begin(),v.end()
#define bp(n) __builtin_popcountll(n)
#define f(i,l,r) for(long long i=l;i<=r;i++)
#define rf(i,r,l) for(long long i=r;i>=l;i--)
#define fast ios_base::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL)
 
template<typename T> ostream& operator<<(ostream &os, const vector<T> &v) { os << '{'; string sep; for (const auto &x : v) os << sep << x, sep = ", "; return os << '}'; }
template<typename T, size_t size> ostream& operator<<(ostream &os, const array<T, size> &arr) { os << '{'; string sep; for (const auto &x : arr) os << sep << x, sep = ", "; return os << '}'; }
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
 
void dbg_out() { cout << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cout << ' ' << H; dbg_out(T...); }
 
 
const int N = 2e5 + 5, mod = 1e9 + 7, bit = 61;
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
int getRand(int l, int r)
{
	uniform_int_distribution<int> uid(l, r);
	return uid(rng);
}
 
class UndirectedEulerPath
{
 
public:
 
	int n;
	vector<set<int>> adj;
	bool is_path = 1;
	bool is_cycle = 1;
	vector<int> path;
 
	UndirectedEulerPath() {}
 
	UndirectedEulerPath(int _n)
	{
		n = _n;
		adj.resize(n + 1);
		path.clear();
	}
 
	void add_edge(int u, int v)
	{
		adj[u].insert(v);
		adj[v].insert(u);
	}
 
	void dfs(int u)
	{
		while (!adj[u].empty())
		{
			int v = *(adj[u].begin());
			adj[u].erase(adj[u].find(v));
			adj[v].erase(adj[v].find(u));
			dfs(v);
			path.push_back(u);
		}
	}
 
	void solve()
	{
		int cntEdges = 0;
		is_path = is_cycle = 1;
		int src = -1, dest = -1, same = 0;
		for (int i = 1; i <= n; i++)
		{
			cntEdges += adj[i].size();
			if ((int)adj[i].size() % 2 == 0)
			{
				same++;
			}
			else if (src == -1)
			{
				src = i;
			}
			else
			{
				dest = i;
			}
		}
		cntEdges >>= 1;
		is_path &= (same == n || same == n - 2);
		if (!is_path)
		{
			is_cycle = 0;
			return;
		}
		if (src == -1)  // Find first vertex having outgoing edge
		{
			for (int i = 1; i <= n; i++)
			{
				if (!adj[i].empty())
				{
					src = i;
				}
			}
		}
		if (src == -1) // All vertices are isolated (m = 0)
		{
			return;
		}
		path.clear();
		path.push_back(src);
		dfs(src);
		is_path &= ((int)path.size() == cntEdges + 1);
		is_cycle &= (is_path && path[0] == path.back() && dest == -1);
	}
 
};
 
signed main()
{
	fast;
 
	int n, m;
	cin >> n >> m;
	UndirectedEulerPath obj(n);
	f(i, 1, m)
	{
		int u, v;
		cin >> u >> v;
		obj.add_edge(u, v);
	}
	obj.solve();
	if (!obj.is_cycle)
	{
		cout << "IMPOSSIBLE" << endl;
		return 0;
	}
	vector<int> res = obj.path;
	int id = -1;
	for (int i = 0; i < (int)res.size(); i++)
	{
		if (res[i] == 1)
		{
			id = i;
			break;
		}
	}
	if (id == -1)
	{
		cout << "IMPOSSIBLE" << endl;
		return 0;
	}
	vector<int> res2;
	for (int i = id; i < (int)res.size(); i++)
	{
		res2.push_back(res[i]);
	}
	for (int i = 1; i <= id; i++)
	{
		res2.push_back(res[i]);
	}
	for (auto &x : res2)
	{
		cout << x << " ";
	}
	cout << endl;
	return 0;
}