Lexicographically Minimal Eulerian Circuit

JSK is planning a New Year trip around town. The town has m intersections (numbered 1 to m) and n streets (numbered 1 to n). Each street connects exactly two distinct intersections and no two streets share the same number. JSK wants to travel along each street exactly once and return to his starting point which is defined as the smaller numbered intersection incident to street 1. In other words, he is looking for an Eulerian circuit in the graph. If more than one such circuit exists, he requires the one whose sequence of street numbers (in the order they are traversed) is lexicographically smallest.

Note that every street is assumed to be similar (i.e. not a dead-end) and any street is reachable from any other. Also, because the streets are narrow, once the car enters a street it cannot make an immediate about-turn. If no Eulerian circuit exists, output a message.

Input Format: The first line contains two integers n and m. The following n lines each contain two integers u and v, meaning that this street connects intersections u and v. The streets are given in order; the first street has number 1, the second number 2, and so on.

Output Format: If there exists an Eulerian circuit starting at the smaller endpoint of street 1, output the sequence of street numbers in the order they are traversed, separated by a single space. If no such circuit exists, output "No Eulerian circuit exists".

inputFormat

The first line contains two integers n and m, where n is the number of streets and m is the number of intersections. Each of the next n lines contains two integers representing the intersections connected by a street. Streets are numbered from 1 to n in the order they are provided.

outputFormat

If an Eulerian circuit exists, output a single line with the sequence of street numbers (edges) that form the lexicographically smallest Eulerian circuit, separated by spaces. Otherwise, output "No Eulerian circuit exists".

sample

3 3
1 2
2 3
1 3

1 2 3