Problem 15: Eulerian Path

Problem Statement: Given a directed graph, determine if an Eulerian path exists and output one if it does.

Input

The first line contains n and m. Next m lines contain two integers u v indicating an edge from u to v.

Output

If an Eulerian path exists, print the path (vertices in order). Otherwise, print "No Eulerian Path".

Examples


Input:
5 5\n1 2\n2 3\n3 1\n1 4\n4 5

Output:
1 2 3 1 4 5

Solution in C++


#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;

int main(){
    int n, m; 
    cin >> n >> m;
    vector<vector<int>> adj(n+1);
    vector<int> outdeg(n+1,0), indeg(n+1,0);
    for(int i=0;i<m;i++){
        int u,v; cin >> u >> v;
        adj[u].push_back(v);
        outdeg[u]++; indeg[v]++;
    }
    int start = 1;
    for(int i=1;i<=n;i++){
        if(outdeg[i]-indeg[i]==1) {start = i; break;}
    }
    stack<int> st;
    vector<int> path;
    st.push(start);
    while(!st.empty()){
        int u = st.top();
        if(!adj[u].empty()){
            int v = adj[u].back();
            adj[u].pop_back();
            st.push(v);
        } else {
            path.push_back(u);
            st.pop();
        }
    }
    reverse(path.begin(), path.end());
    if(path.size() != m+1){
        cout << "No Eulerian Path";
    } else {
        for(auto v : path) cout << v << " ";
    }
    return 0;
}