Shared code

#include <bits/stdc++.h>
 
using namespace std;
 
#define in(a)                                                                  \
    for (auto &x : a)                                                          \
        cin >> x;
#define rep(i, a, b) for (int i = a; i < b; i++)
#define out(a)                                                                 \
    for (auto x : a)                                                           \
        cout << x << " ";
#define pb push_back
#define int long long
typedef vector<int> vi;
typedef pair<int, int> pii;
 
/*
    Eulerian cycle: all nodes need to have even outdegrees
    Eulerian path: all nodes need to have even outdegrees and exactly two nodes
    can have odd degrees
 
    need to handle edge deletion
    make a visited array with size of number of edges.
    while inserting keep track of index of each edge.
    so while traversing check if edge was visited, if true then continue
    else break
 
    also it's better to remove the nodes from adj[x] who we have already visited
    since otherwise we'll be iterating through them multiple times.
 
    in cases like this
 
           1
        //   \\
       2       3
 
       imagine instead of 2 and 3 we have like 10**5 nodes,
       it's going to be O(n^2)
 
       thus pop those nodes and retain O(n)
*/
vector<vector<pair<int, int>>> adj;
vector<int> path;
void dfs(int x, vector<int> &visited)
{
    while (!adj[x].empty()) {
        pair<int, int> next = adj[x].back();
        adj[x].pop_back();
        if (visited[next.second])
            continue;
        visited[next.second] = 1;
        dfs(next.first, visited);
    }
    path.push_back(x);
}
void solve()
{
    int n, m;
    cin >> n >> m;
    adj.resize(n + 1);
    vector<int> indeg(n + 1);
    for (int i = 0; i < m; i++) {
        int x, y;
        cin >> x >> y;
        indeg[x]++;
        indeg[y]++;
        // use m as an index, to mark which edges are done.
        adj[x].push_back({y, i});
        adj[y].push_back({x, i});
    }
    bool exists = true;
    for (int i = 1; i <= n; i++) {
        exists &= (indeg[i] % 2 == 0);
    }
    if (!exists) {
        cout << "IMPOSSIBLE\n";
        return;
    }
 
    vector<int> visited(m, 0); // to mark edges as visited
    dfs(1, visited);
    if (path.size() == m + 1) {
        out(path);
        cout << '\n';
    }
    else {
        cout << "IMPOSSIBLE\n";
    }
}
 
int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    int t = 1;
    // cin >> t;
 
    while (t--) {
        solve();
    }
 
    return 0;
}