4249. 「NordicOI 2019」Graph Ordering

时间限制：1000 ms
内存限制：512 MiB
通过：4
提交：20

题目描述

题目译自 NordicOI 2019 T3 「Graph Ordering」

你有一个包含 $n$ 个节点的无向连通图。节点编号为 $1, 2, \dots, n$。

我们来考虑节点的一个排列。排列中的第一个节点称为源节点，最后一个节点称为汇节点。此外，我们称一条路径是合法的，如果对于路径上的所有边 $(a,b)$，要从节点 $a$ 移动到节点 $b$，节点 $a$ 在排列中的位置必须位于节点 $b$ 之前。

你的任务是找到一个排列，使得：

1. 从源节点到每个节点都有一条合法的路径；
2. 从每个节点到汇节点都有一条合法的路径。

或者判断不存在这样的排列。

输入格式

第一行有两个整数 $n$ 和 $m$，表示节点数和边数。

接下来有 $m$ 行描述这些边。每行有两个整数 $a$ 和 $b$，表示节点 $a$ 和节点 $b$ 之间有一条边。

保证图是连通的，不包含自环，并且每对节点之间最多有一条边。

输出格式

输出任意一个合法的节点排列。如果不存在合法的方案，输出 IMPOSSIBLE。

样例 1

输入

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

输出

4 2 3 1 5

样例 2

输入

4 3
1 2
3 2
4 2

输出

IMPOSSIBLE

数据范围与提示

详细子任务附加限制及分值如下表所示。