Lexicographically Smallest Eulerian Path in a Directed Graph

You are given a directed graph with n vertices and m edges. Your task is to find an Eulerian path whose sequence of vertices is lexicographically smallest among all possible Eulerian paths. An Eulerian path is a path that visits every edge exactly once.

The necessary and sufficient conditions for the existence of an Eulerian path in a directed graph are given by the following (in \(\LaTeX\)):

\(\begin{cases} \text{For all vertices } v,\; indeg(v)=outdeg(v) \quad \text{or}\\ \exists\; u: outdeg(u)=indeg(u)+1 \text{ and } \exists\; v: indeg(v)=outdeg(v)+1 \end{cases}\)

If the graph contains an Eulerian circuit then you should output the lexicographically smallest cycle starting at the smallest vertex that has an outgoing edge.

Note: It is guaranteed that the given input will have an Eulerian path or circuit.

inputFormat

The first line contains two integers n and m representing the number of vertices and edges respectively.

The following m lines each contain two integers u and v indicating there is a directed edge from vertex u to vertex v. Vertices are numbered from 1 to n.

outputFormat

Output the vertices in the lexicographically smallest Eulerian path, separated by a single space.

sample

3 3
1 2
2 3
3 1

1 2 3 1