#include <algorithm>
#include <fstream>
#include <iostream>
#include <vector>
#include <unordered_set>

class Graph
{
public:

    Graph(unsigned vertices)
    {
    }

    unsigned get_vertex_count() const
    {
    }

    void add_edge(unsigned u, unsigned v)
    {
    }

    void remove_edge(unsigned u, unsigned v)
    {
    }
    
    std::vector<unsigned> get_neighbours(unsigned v) const
    {
    }

    unsigned out_degree(unsigned v) const
    {
    }

    unsigned in_degree(unsigned v) const
    {
    }

private:

    // Lägg till datamedlemmar

};

// Antar att grafen är sammanhängande
bool has_euler_circuit(Graph const& graph)
{
    for (unsigned v { 0 }; v < graph.get_vertex_count(); ++v)
    {
        if (graph.out_degree(v) != graph.in_degree(v))
            return false;
    }
    return true;
}

// Hierholzer's algorim
std::vector<unsigned> find_euler_circuit(Graph graph)
{
    std::vector<unsigned> circuit { };

    if (!has_euler_circuit(graph))
        return circuit;
    
    // börja med nod 0
    std::vector<unsigned> stack { 0 };

    // upprepad djupet-först-sökning för att hitta en krets som går igenom
    // vardera nod, en euler krets besöker alla bågar, så vi måste besöka
    // alla bågar i kretsen.
    while (!stack.empty())
    {
        unsigned current { stack.back() };

        std::vector<unsigned> neighbours { graph.get_neighbours(current) };

        if (neighbours.empty())
        {
            // om det inte finns några grannar har vi hittat alla vägar, lägg
            // till den nuvarande noden i vår producerade krets.
            circuit.push_back(current);
            stack.pop_back();
        }
        else
        {
            // om det finns grannar lägger vi till den i stacken och tar sedan
            // bort bågen i grafen, detta för att inte besöka samma båge igen.
            unsigned next { neighbours.back() };
            graph.remove_edge(current, next);
            stack.push_back(next);
        }
    }

    std::reverse(circuit.begin(), circuit.end());
    return circuit;
}

int main(int argc, char** argv)
{
    if (argc < 2)
    {
        std::cerr << "USAGE: " << argv[0] << " GRAPH" << std::endl;
        return 1;
    }

    std::ifstream ifs { argv[1] };
    if (!ifs)
    {
        std::cerr << "ERROR: Unable to open " << argv[1] << std::endl;
        return 2;
    }

    unsigned vertices { };
    unsigned edges    { };

    ifs >> vertices >> edges;

    Graph graph { vertices };

    // read all edges
    for (unsigned i { 0 }; i < edges; ++i)
    {
        unsigned begin { };
        unsigned end   { };
        ifs >> begin >> end;
        graph.add_edge(begin, end);
    }

    std::vector<unsigned> circuit { find_euler_circuit(graph) };

    if (circuit.empty())
        std::cout << "No eulerian circuit!" << std::endl;
    else
    {
        std::cout << circuit[0];
        for (std::size_t i { 1 }; i < circuit.size(); ++i)
            std::cout << " -> " << circuit[i];
        std::cout << std::endl;
    }
}