Problem B
Trip 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?


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.


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
Sample Input 2 Sample Output 2
4 4
1 2
1 3
2 3
3 4

Please log in to submit a solution to this problem

Log in