#include<vector>
#include<deque>
#include<algorithm>


struct EulerGraph {
    struct Arc {
        int u;
        int v;
    };
    struct Node {
        int index;
        std::vector<Arc*> arcs;  // Arcs that exit this node
    };
    
    std::vector<Node> nodes_;
    std::deque<Arc> arcs_;  // We use deque to avoid pointer invalidation when capacity is exceeded
    
    EulerGraph(int num_nodes) {
        nodes_.resize(num_nodes);
        for(int i=0; i<num_nodes; i++) {
            nodes_[i].index = i;
        }
    }
    
    void add_arc(int u, int v) {
        arcs_.push_back({u, v});
        nodes_[u].arcs.push_back(&arcs_.back());
    }
    
    std::vector<int> get_eulerian_path(int start = 0) {
        std::vector<int> eulerian_path;  // The constructed eulerian cycle. Initially reversed
        std::vector<int> arc_i(nodes_.size(), 0);  // The current arc we are looking at for each node
        std::vector<int> node_stack = {start};  // The current path we are on
        
        while(node_stack.size() > 0) {
            int node_i = node_stack.back();
            Node& node = nodes_[node_i];
            
            if(arc_i[node_i] < (int)node.arcs.size()) {  // We haven't traversed all arcs on that node yet
                node_stack.push_back(node.arcs[arc_i[node_i]]->v);
                arc_i[node_i]++;
            } else {  // We have traversed all arcs for this node, so add the node to Eulerian cycle
                eulerian_path.push_back(node_i);
                node_stack.pop_back();
            }
        }
        std::reverse(eulerian_path.begin(), eulerian_path.end());
        return eulerian_path;
    }
};


int main() {
    EulerGraph graph(5);
    graph.add_arc(0, 1);
    graph.add_arc(1, 2);
    graph.add_arc(2, 0);
    graph.add_arc(1, 3);
    graph.add_arc(3, 4);
    graph.add_arc(4, 1);
    std::vector<int> result = graph.get_eulerian_path();
    
    return 0;
}