Hide

Problem B
Eulerian Path

Input

The input consists of several test cases. Each test case starts with a line with two non-negative integers, $2 \le n \le 10\, 000$ and $1 \le m \le 50\, 000$, separated by a single space, where $n$ is the numbers of nodes in the graph and $m$ is the number of edges. Nodes are numbered from $0$ to $n-1$. Then follow $m$ lines, each line consisting of two (space-separated) integers $u$ and $v$ indicating that there is an edge from $u$ to $v$ in the graph.

Input will be terminated by a line containing 0 0, this line should not be processed.

Output

For each test case, output a line consisting of a space-separated list of the nodes visited by an Eulerian path if one exists (if there are multiple Eulerian paths, any one is acceptable, so for the second case below, 1 0 1 is also a valid solution), or the word Impossible if no Eulerian path exists.

Sample Input 1 Sample Output 1
4 4
0 1
1 2
1 3
2 3
2 2
0 1
1 0
2 1
0 1
0 0
Impossible
0 1 0
0 1

Please log in to submit a solution to this problem

Log in