7592: [CSES Problem Set] Teleporters Path
[Creator : ]
Description
A game has $n$ levels and $m$ teleportes between them. You win the game if you move from level $1$ to level nn using every teleporter exactly once.
Can you win the game, and what is a possible way to do it?
Can you win the game, and what is a possible way to do it?
Input
The first input line has two integers $n$ and $m$: the number of levels and teleporters. The levels are numbered $1,2,\dots,n$.
Then, there are $m$ lines describing the teleporters. Each line has two integers $a$ and $b$: there is a teleporter from level $a$ to level $b$.
You can assume that each pair $(a,b)$ in the input is distinct.
Then, there are $m$ lines describing the teleporters. Each line has two integers $a$ and $b$: there is a teleporter from level $a$ to level $b$.
You can assume that each pair $(a,b)$ in the input is distinct.
Output
Print $m+1$ integers: the sequence in which you visit the levels during the game. You can print any valid solution.
If there are no solutions, print "IMPOSSIBLE".
If there are no solutions, print "IMPOSSIBLE".
Constraints
$2≤n≤10^5$
$1 \le m \le 2 \cdot 10^5$
$1 \le a,b \le n$
$1 \le m \le 2 \cdot 10^5$
$1 \le a,b \le n$
Sample 1 Input
5 6
1 2
1 3
2 4
2 5
3 1
4 2
Sample 1 Output
1 3 1 2 4 2 5