Hide

# Problem DTrip Planning

Lars is planning to do a backpacking tour by train throughout $N$ cities in Europe. He has a list of train lines numbered from $1$ to $M$ that each goes back and forth between some pair of cities, no two between the same pair. He wants to visit the cities in the order $1$, $2$, $\dots$, $N$, finally returning back to his home in city $1$.

Since Lars has limited vacation days, he only has time to take exactly $N$ direct trains during his trip. Can you determine if this is possible, and tell Lars the numbers of the train lines he should take?

## Input

The first and only line of input contains integers $N$ ($2 \le N \le 10^6$), the number of cities Lars wants to visit, and $M$ ($1 \le M \le 10^6$), the number of train lines.

The next $M$ lines contains a pair of integers $1 \le a \neq b \le N$ representing a train line between cities $a$ and $b$. The train lines are numbered $1$ to $M$ in the order that they appear in the input. No two train lines go between the same pair of cities.

## Output

If Lars cannot make the trip, output impossible. Otherwise, output a sequence of $N$ lines. These should be the numbers of the train lines Lars should take in order of travel.

Sample Input 1 Sample Output 1
3 3
1 2
1 3
2 3

1
3
2

Sample Input 2 Sample Output 2
4 4
1 2
1 3
2 3
3 4

impossible

CPU Time limit 8 seconds
Memory limit 1024 MB
Statistics Show