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

using namespace std;

class Graph{
protected:
    int m_nodes;
};

class Multigraph:Graph{
private:
    vector< vector<int> > m_nodes_edges;
    vector< pair<int,int> > m_edges;
public:
    //citirea multigrafului

    void read_multigraph(char *file);

    //euler(nod) -> determina un ciclu eulerian din multigraf si il returneaza, sau returneaza -1 daca graful nu are niciun ciclu eulerian

    vector<int> euler(int nod);
private:
    bool check_even_degrees();
};

//METODE PUBLICE

//citirea unui multigraf

void Multigraph::read_multigraph(char *file) {
    ifstream f(file);

    int number_of_edges;

    vector<int> aux;

    //citim numarul de noduri si numarul de muchii

    f >> m_nodes >> number_of_edges;

    //initializam matricea de muchii si vectorii cu nodurile sursa si nodurile destinatie ale muchiilor

    m_nodes_edges.assign(m_nodes + 1, aux);
    m_edges.resize(number_of_edges + 1);

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

        //citim fiecare muchie in parte

        int x,y;
        f >> x >> y;

        //actualizam matricea de muchii: la x si la y marcam existenta muchiei i

        m_nodes_edges[x].push_back(i);
        m_nodes_edges[y].push_back(i);

        //marcam cum exact este aceasta muchie: de la x la y, deci actualizam vectorul de noduri de sursa ( adaugand x)
        // si cel de noduri destinatie (adaugand y)

        m_edges[i] = make_pair(x,y);
    }

}

vector<int> Multigraph::euler(int nod) {

    vector<int> euler_cycle;

    //una din conditiile ca un graf sa fie eulerian este sa aiba toate nodurile cu graduri pare, asa ca testam acest lucru

    if(!this->check_even_degrees()){

        euler_cycle.push_back(-1);
        return euler_cycle;
    }

    stack<int> nodes;
    vector<int> visited_edges;

    //initializam vectorul de muchii vizitate: initial toate sunt nevizitate

    visited_edges.assign(m_edges.size(), 0);

    //adaugam in stiva cu ciclul format momentan primul nod: cel dat

    nodes.push(nod);

    //cat timp stiva nu e goala <=> cat timp mai avem noduri in ciclul format

    while(!nodes.empty()){

        //preluam nodul curent din ciclul format

        int current_node;

        current_node = nodes.top();

        //daca nodul curent are vecini, luam muchia catre un vecin aleator al nodul curent - aici ultimul, pentru a-l putea elimina usor

        if(m_nodes_edges[current_node].size() != 0){

            int random_edge;

            random_edge = m_nodes_edges[current_node].back();

            //eliminam muchia aleasa

            m_nodes_edges[current_node].pop_back();

            //daca muchia nu a mai fost vizitata pana acum, atunci luam muchia care pleaca din el si adaugam nodul destinatie in stiva cu ciclul format

            if(visited_edges[random_edge] == 0){

                //marcam muchia ca vizitata

                visited_edges[random_edge] = 1;

                //adaugam vecinul la care ne trimite muchia in stiva cu ciclul eulerian curent

                nodes.push(m_edges[random_edge].first ^ m_edges[random_edge].second ^ current_node);
            }
        } else {
            //daca nodul curent nu are vecini, il scoatem din stiva cu ciclul eulerian format si il adaugam in rezultat

            nodes.pop();
            euler_cycle.push_back(current_node);
        }
    }

    return euler_cycle;
}

//METODE PRIVATE

//check_even_degrees -> verifica daca toate nodurile muligrafului au grad par

bool Multigraph::check_even_degrees() {

    for(int i = 1; i <= m_nodes; i++){
        if(m_nodes_edges[i].size() % 2 == 1){
            return false;
        }
    }

    return true;

}

//HELPERE

void print_vector(vector<int> v, char *file){
    ofstream g(file);
    vector<int>::iterator it;

    for(it = v.begin(); it != v.end(); it++){
        g << *it << " ";
    }
}

int main() {

    Multigraph g;
    vector<int> euler_cycle;

    g.read_multigraph("../ciclueuler.in");

    euler_cycle = g.euler(1);

    print_vector(euler_cycle, "../ciclueuler.out");

    return 0;
}