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

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
    while (numberOfEdges != 0) {
        file >> x >> y;
        addEdgeUnoriented(x - 1, y - 1);
        numberOfEdges--;
    }
}

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 Graph::eulerFunction(int node, std::vector<int> &cycles) {

    while(!adjacentList[node].empty()) {

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

        if(node != neighbour) {

            auto find = std::find(adjacentList[neighbour].begin(), adjacentList[neighbour].end(), node);

            if (find != adjacentList[neighbour].end()) {

                *find = adjacentList[neighbour].back();
                adjacentList[neighbour].pop_back();
            }
        }
        eulerFunction(neighbour, cycles);
    }
    cycles.push_back(node);
}

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

    std::vector<int> result;
    result.reserve(numberOfElements);

    eulerFunction(0, result);

    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 << " ";
        }
    }
    return 0;
}