#include <bits/stdc++.h>
using namespace std;

#define ever ;true;
#define Dbug(x) cout << "Debug: " << #x << " = " << x << endl
#define _ << ", " <<
#define ll long long

vector<int> shift(vector<int> C, int starting_vertex) {
    C.pop_back();
    while (C[0] != starting_vertex) {
        rotate(C.begin(), C.begin() + 1, C.end());
    }
    C.push_back(C[0]);
    return C;
}

vector<int> EulerCircuit(vector<int> C, vector<vector<bool>> G) {
    // Deletes edges in C out of G
    for (int i = 0; i < (int)C.size() - 1; i++) {
        int x = C[i], y = C[i + 1];
        G[x][y] = false, G[y][x] = false;
    }

    // Check if there is any edge left in G, if not return C.
    bool finished = true;
    for (auto row : G)
        for (auto col : row)
            if (col)
                finished = false;
    if (finished)
        return C;

    // Find the next sharing vertices between C and G.
    int next_sharing_vertex;
    bool found = false;
    for (auto in_C : C) {
        for (int i = 0; i < G[in_C].size() && !found; i++)
            if (G[in_C][i])
                next_sharing_vertex = in_C, found = true;
        if (found)
            break;
    }
    // Shifts the next sharing vertex to the beginning of C.
    if (found)
        C = shift(C, next_sharing_vertex);
    // If C and G has no sharing vertices, i.e the start, then use the first non-lonely vertex in G.
    else {
        for (int i = 0; i < G.size() && !found; i++)
            for (int j = 0; j < G[i].size() && !found; j++)
                if (G[i][j])
                    next_sharing_vertex = i, found = true;
                else if (G[j][i])
                    next_sharing_vertex = j, found = true;
        C.push_back(next_sharing_vertex);
    }

    vector<int> _C {next_sharing_vertex};
    while (_C.size() == 1 || _C.front() != _C.back()) {
        int back = _C.back();
        for (int i = 0; i < G[back].size(); i++)
            if (G[back][i] && i != _C[_C.size() - 2]) {
                _C.push_back(i);
                break;
            }
    }

    for (int i = 1; i < _C.size(); i++)
        C.push_back(_C[i]);

    return EulerCircuit(C, G);
}

int main()
{
    cout << "Please input the number of vertices: ";
    int V; cin >> V;
    vector<vector<bool>> G;
    G.resize(V);
    for (int i = 0; i < V; i++)
        G[i].resize(V);
    for (int i = 0; i < V; i++)
        for (int j = 0; j < V; j++)
            G[i][j] = false;
    cout << "Please input the number of edges: ";
    int E; cin >> E;
    for (int i = 0; i < E; i++) {
        cout << "Please input 2 vertices of this edge: ";
        int x, y; cin >> x >> y;
        G[x][y] = true; G[y][x] = true;
    }

    vector<int> res = EulerCircuit({}, G);
    for (auto out : res)
        cout << out << " ";
    cout << "\n";
}