Teleporters Path

题目描述

一个游戏有 n 个关卡和 m 条传送门。 如果你从关卡 1 移动到关卡 n 且每条传送门恰好使用一次，则你赢得游戏。\n你能赢得游戏吗？并给出一种可能的实现方式。

输入格式

第一行输入包含两个整数 n 和 m：关卡数和传送门数。关卡编号为 1,2,$\dots$,n。\n接下来有 m 行描述传送门。每行包含两个整数 a 和 b：存在一条从关卡 a 到关卡 b 的传送门。\n你可以假设输入中的每一对 (a,b) 都是不同的。

输出格式

输出 m+1 个整数：你在游戏中访问关卡的顺序。你可以输出任意一个合法的解。\n如果不存在解，输出 "IMPOSSIBLE"。

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

1 3 1 2 4 2 5

提示

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

标签: CSES1693|图论

来源

CSES1693|图论