#include <iostream>
#include <stack>
#include <queue>
#include <algorithm>
#include <vector>
#include <fstream>
#include <tuple>

class Graph {
private:
// #pragma region attributes

    int numberOfElements; // the number of nodes from the graph
    int numberOfEdges; // number of edges of the graph
    int diameterOfTree; // The diameter of the tree, used for InfoArena
    int lastNode;
    bool isOriented; // bool that checks if the graph is oriented / unoriented (oriented -> true, unoriented -> false)
    // todo: schimba std::vector
    std::vector<int> adjacentList[100000]; // implementing the graph using an array of adjacentLists


// #pragma endregion

// #pragma region private functions that help at building the graph
    void addEdgeOriented(int a, int b); // using this function at reading if we are working with an oriented graph
    void addEdgeUnoriented(int a, int b); // using this function at reading if we are working with an unoriented graph
    void eulerFunction(int node, std::vector<int> &cycles);
// #pragma endregion

public:
    // todo: FUNCTII CARE RETURNEAZA!
// #pragma region public functions related to the class

    Graph(int numberOfElements, int numberOfEdges, bool isOriented);
    Graph();

    // void checkTypeAndRead(); // check the type of the graph
    void readOriented(std::ifstream &file); // reading the data for an oriented graph
    void readUnoriented(std::ifstream &file); // reading the data for an unoriented graph
    void printGraph(); // output the content from the graph
    void dfsRec(int node); // recursive definition of the DFS for the given node.
    void dfsIter(int node); // iterative definitions of the DFS for the given node.
    void bfs(int node); // BFS for the given node, outputs the distances;

    int getDiameter(); // getter for the diameter
    int getLastNode(); // getter for the last node after the bfs

    int numberOfConnectedComponents(); // returns the number of connected components in the Graph
    void topologicalSort(); // topological sort using Kahn's Algorithm
    bool checkHavelHakimi(std::vector<int>& nodeDegrees); // returns the value of the Havel Hakimi algorithm
    std::vector<int> getEulerianCycle();

    void royFloydAlgorithm(int weightMatrix[100][100]); // for solving the royfloyd algorithm

// #pragma endregion

};

// #pragma region constructors
Graph::Graph(int numberOfElements, int numberOfEdges, bool isOriented) : numberOfElements(numberOfElements), numberOfEdges(numberOfEdges), isOriented(isOriented) {}
Graph::Graph() {
    numberOfElements = 0;
    isOriented = false;
}

// #pragma endregion

// #pragma region functions that help at reading and writing

int Graph::getDiameter() {
    return diameterOfTree;
}
int Graph::getLastNode() {
    return lastNode;
}

void Graph::addEdgeOriented(int a, int b) {
    if(a != b) {
        adjacentList[a].push_back(b);
    }
}

void Graph::addEdgeUnoriented(int a, int b) {
    if(a == b) {
        adjacentList[a].push_back(b); // solving duplicates
    }
    else {
        adjacentList[a].push_back(b);
        adjacentList[b].push_back(a);
    }

}

void Graph::readOriented(std::ifstream &file) {

    // int x, y; // for reading the edges
    // while(edges != 0) {
    //     file >> x >> y;
    //     addEdgeOriented(x, y);
    //     edges--;
    // }
}

void Graph::readUnoriented(std::ifstream &file) {


    int x, y; // for reading the edges
    int cNumberOfEdges=numberOfEdges;
    
    while (cNumberOfEdges != 0) {

        file >> x >> y;

        addEdgeUnoriented(x, y);

        cNumberOfEdges--;

    }

}


// void Graph::printGraph() {
//     for(int node = 1; node <= numberOfElements; node++) {
//         std::cout << "Nodul " << node << " are lista:";
//         for(auto x : adjacentList[node]) {
//             std::cout << "->" << x;
//         }
//         std::cout << "\n";
//     }
// }

// #pragma endregion

// #pragma region graph algorithms

// void Graph::royFloydAlgorithm(int weightMatrix[100][100]) {
//     for(int k = 0; k < numberOfElements; k++) {
//         for(int i = 0; i < numberOfElements; i++) {
//             for(int j = 0; j < numberOfElements; j++) {
//                 if(
//                         i != j &&
//                         weightMatrix[i][k] &&
//                         weightMatrix[k][j] &&
//                         (weightMatrix[i][j] > weightMatrix[i][k] + weightMatrix[k][j] || !weightMatrix[i][j])

//                         ) {
//                     weightMatrix[i][j] = weightMatrix[i][k] + weightMatrix[k][j];
//                 }
//                 // if(
//                 //         weightMatrix[i][k] &&
//                 //         weightMatrix[k][j] &&
//                 //         (weightMatrix[i][j] > weightMatrix[i][k] + weightMatrix[k][j] || !weightMatrix[k][j] && i != j) -> greseala i!=j in par.
//                 //     )
//                 //     {
//                 //         weightMatrix[i][j] = weightMatrix[i][k] + weightMatrix[k][j];
//                 //     }
//             }
//         }
//     }
// }

// DFS -> ITERATIVE AND RECURSIVE
void Graph::dfsRec(int node) {

    int visitedNodes[100000] = {0};

    if(visitedNodes[node] == 1){
        return;
    }
    visitedNodes[node] = 1;
    std::cout << node << " ";
    for(int adjacentNode : adjacentList[node]) {
        dfsRec(adjacentNode); // we are using the app's stack to traverse the graph
    }
}

void Graph::dfsIter(int node) {

    int visitedNodes[100000] = {0};

    std::stack<int> nodeStack;
    // 1. push the node
    nodeStack.push(node);
    visitedNodes[node] = 1;
    // std::cout << node << " ";

    // 2. Iterate through the adjacentList
    while(!nodeStack.empty()){
        // verify the top and then pop it.
        int top = nodeStack.top();
        if(visitedNodes[top] == 0) {
            // std::cout << top << " ";
            visitedNodes[top] = 1;
        }
        nodeStack.pop();

        for(int theOtherNodes : adjacentList[top]) {
            if(visitedNodes[theOtherNodes] == 0) {
                nodeStack.push(theOtherNodes);
            }
        }
    }
}

// INFOARENA: BFS
// void Graph::bfs(int node) {

//     int visitedNodes[100000] = {0}, nodeDegree[100000] = {0};
//     int distance[100000] = {0};

//     std::queue<int> nodeQueue;
//     visitedNodes[node] = 1;
//     nodeQueue.push(node);

//     // Modify the BFS for InfoArena
//     // you need a counter array so that you can measure the distance
//     int counter[100000] = {0};

//     counter[node] = 1; // set the starting node's counter to 1


//     while(!nodeQueue.empty()) {
//         // pop the front
//         int front = nodeQueue.front();
//         // find the neighbours of the current node
//         for(auto theOtherNodes : adjacentList[front]) {
//             // theOtherNodes = nod[el][i]
//             // contor = counter;
//             if(visitedNodes[theOtherNodes] == 0) {
//                 // mark them and then increase the distance between the nodes
//                 nodeQueue.push(theOtherNodes);
//                 visitedNodes[theOtherNodes] = 1;

//                 // modification for InfoArena
//                 counter[theOtherNodes] = counter[front] + 1; // increase the counter for the visited node.

//                 diameterOfTree = counter[theOtherNodes];
//                 lastNode = theOtherNodes;
//             }
//         }
//         nodeQueue.pop();
//     }
//     //output the distances
//     // for(int i = 0; i < numberOfElements; i++) {
//     //     if(visitedNodes[i] != 0) {
//     //         std::cout << distance[i] << " ";
//     //     }
//     //     else {
//     //         std::cout << -1 << " ";
//     //     }
//     // }
// }

//INFOARENA -> Connected components
// int Graph::numberOfConnectedComponents() {

//     int visitedNodes[100000] = {0};

//     int counter = 0;
//     // traverse the nodes, if you find anything that is not visited, then increase the counter and do a DFS.
//     for(int i = 0; i < numberOfElements; i++) {
//         if(visitedNodes[i] == 0) {
//             counter++;
//             // calling the iterative version
//             dfsIter(i);
//         }
//     }
//     return counter;
// }

//INFOARENA -> Topological Sort (with BFS, tried with DFS and it doesn t work propely)
// void Graph::topologicalSort() {
//     int visitedNodes[100000] = {0}, nodeDegree[100000] = {0};

//     // create a queue
//     std::queue<int> nodeQueue;
//     std::vector<int> result;

//     // calculate the degree of every node
//     for(int i = 0; i < numberOfElements; i++) {
//         for(int j : adjacentList[i]) {
//             nodeDegree[j] += 1; // increasing the IN degree
//         }
//     }

//     // enqueue all the nodes with degree = 0;

//     for(int i = 0; i < numberOfElements; i++) {
//         if(nodeDegree[i] == 0) {
//             nodeQueue.push(i);
//         }
//     }

//     while(!nodeQueue.empty()) {
//         // dequeue the front element and push it into the result
//         int front = nodeQueue.front();
//         nodeQueue.pop();

//         result.push_back(front);

//         for(int newNode : adjacentList[front]) {
//             // decrease the degree of the neighbours of the currently dequed element
//             nodeDegree[newNode]--;
//             // if the degree is zero, then enqueue it
//             if(nodeDegree[newNode] == 0) {
//                 // enqueue all the nodes with degree == 0
//                 nodeQueue.push(newNode);
//             }
//         }
//     }

//     for(int i : result) {
//         std::cout << i + 1 << " "; // output the vector
//     }
// }


// Check the Havel Hakimi for a given array
// bool Graph::checkHavelHakimi(std::vector<int>& nodeDegrees) {
//     // used the STL vector because it's easier than working with arrays.

//     while(true) {
//         // if the nodeDegrees vector is empty or it only contains zeroes, then it's valid
//         if(nodeDegrees.empty() || std::all_of(nodeDegrees.begin(), nodeDegrees.end(), [](int i) {return i == 0;})) {
//             return true;
//         }

//         // sort the vector
//         std::sort(nodeDegrees.begin(), nodeDegrees.end());

//         std::cout << "\n";
//         int lastElement = nodeDegrees[nodeDegrees.size() - 1];
//         if(lastElement > nodeDegrees.size() - 1) {
//             return false;
//         }

//         nodeDegrees.erase(nodeDegrees.begin() + nodeDegrees.size() - 1);

//         for(int i =  nodeDegrees.size() - 1; i > nodeDegrees.size() - 1 - lastElement ; i--) {
//             if(nodeDegrees[i] > 0) {
//                 nodeDegrees[i]--;
//             }
//             else {
//                 return false;
//             }
//         }
//     }
// }

//https://infoarena.ro/problema/ciclueuler
//euler(nod v)
//    cat timp(v are vecini)
//        w = un vecin aleator al lui v
//        sterge_muchie(v, w)
//        euler(w)
//    sfarsit cat timp
//    adauga v la ciclu

// void f(params) {     TEMPLATE FOR TRANSFORMING RECURSIVE TO ITERATIVE
//   stack st;
//   st.push(params);
//   while(!stack.empty) {
//     params_tmp = stack.pop();
//     // you re gonna do a push here instead of the recursive call
//     while(...)
//       stack.push(new_params);
//   }
// }

void Graph::eulerFunction(int node, std::vector<int> &cycles) {
    // verifying the parity for every node 
    for (int i=0;i<=numberOfElements; i++) {
        int co=0;
        for(auto& neighbour : adjacentList[i]){
            if(neighbour!=i)
                co++;
            else
                co+=2;
        }
        if(co%2==1)
            return;
    }

    std::stack<int> nodeStack;
    cycles.push_back(node);
    nodeStack.push(node);

    while (!nodeStack.empty()) {

        int currentNode = nodeStack.top();
        // std::vector<int> currentCycles = std::get<1>(currentTuple);
//        nodeStack.pop();

        if (!adjacentList[currentNode].empty()) {

            int neighbour = adjacentList[currentNode].back();
            adjacentList[currentNode].pop_back();

         if (currentNode != neighbour) {

            auto find = std::find(adjacentList[neighbour].begin(), adjacentList[neighbour].end(), currentNode);
            if (find != adjacentList[neighbour].end()) {
                *find = adjacentList[neighbour].back();
                adjacentList[neighbour].pop_back();
            }
         }
            cycles.push_back(neighbour);
            nodeStack.push(neighbour);
        } else {
            nodeStack.pop();
        }
//        cycles.push_back(currentNode);
    }
}

std::vector<int> Graph::getEulerianCycle() {

    std::vector<int> result;
    // std::stack<std::tuple<int, std::vector<int>>> nodeStack;
    result.reserve(numberOfElements);

    eulerFunction(1, result);

    if(result.size()!=numberOfEdges+1)
        return {};

    for(int i = 0; i < numberOfElements; i++) {

        if(!adjacentList[i].empty()){
            return {};
        }
    }

    for(auto& i: result) {
        i++;
    }


    return result;

}

std::ifstream f("ciclueuler.in");
std::ofstream o("ciclueuler.out");

int main() {
    
    int nodes, edges;
    f >> nodes >> edges;
    Graph *graph = new Graph(nodes, edges, false);
    graph->readUnoriented(f);
    auto result = graph->getEulerianCycle();
    if(result.empty()) {
        o << -1;
    }
    else {
        result.pop_back(); // popping because it comes back to the root
        for(auto i : result) {
            o << i - 1 << " ";
        }
    }
    return 0;
}