链接: https://cses.fi/problemset/task/1693

板块: Graph Algorithms

时限: 1.00 s ｜ 内存: 512 MB

题目描述

一个游戏有 $n$ 个关卡和它们之间的 $m$ 个传送器。如果你恰好使用每个传送器一次，从关卡 $1$ 移动到关卡 $n$，你就赢得了游戏。

你能赢得游戏吗？如果可以，一种可能的做法是什么？

输入

第一行输入包含两个整数 $n$ 和 $m$：关卡数量和传送器数量。关卡编号为 $1,2,\dots,n$。

接着有 $m$ 行描述传送器。每行包含两个整数 $a$ 和 $b$：存在一条从关卡 $a$ 到关卡 $b$ 的传送器。

你可以假设输入中每对 $(a,b)$ 都是不同的。

输出

输出 $m+1$ 个整数：游戏过程中你访问关卡的先后顺序。你可以输出任意合法解。

如果没有解，输出 "IMPOSSIBLE"。

数据范围

$2 \le n \le 10^5$ $1 \le m \le 2 \cdot 10^5$ $1 \le a,b \le n$

样例输入

5 6
1 2
1 3
2 4
2 5
3 1
4 2

样例输出

1 3 1 2 4 2 5