背景

Special Judge 来自于 LibreOJ。

题目描述

给定一个具有 $n$ 个节点的无向连通图。节点编号为 $1, 2, \ldots, n$。

考虑一个节点的排序。排序中的第一个节点称为源点，最后一个节点称为汇点。此外，一条路径被称为有效的，当且仅当我们从节点 $a$ 移动到节点 $b$ 时，节点 $a$ 在排序中位于节点 $b$ 之前。

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

• （1）从源点到每个节点都存在一条有效路径，并且
• （2）从每个节点到汇点都存在一条有效路径；

或者判断不可能创建这样的排序。

输入格式

• 第一行有两个整数 $n$ 和 $m$：分别表示节点数和边数。
• 之后是 $m$ 行，描述图中的边。每行包含两个整数 $a$ 和 $b$：表示节点 $a$ 和 $b$ 之间有一条边。

保证图是连通的，没有自环，并且任意两个节点之间最多有一条边。

输出格式

输出任意一个有效的节点排序。如果无解，则输出“IMPOSSIBLE”。

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

4 2 3 1 5

4 3
1 2
3 2
4 2

IMPOSSIBLE

提示

子任务 1（7 分）

• $2 \leq n \leq 10^5$
• 图是一棵树。

子任务 2（29 分）

• $2 \leq n \leq 100$
• $1 \leq m \leq 200$

子任务 3（18 分）

• $2 \leq n \leq 2000$
• $1 \leq m \leq 5000$

子任务 4（21 分）

• $2 \leq n \leq 10^5$
• $1 \leq m \leq 2 \cdot 10^5$
• 保证存在一个有效的排序，其中节点 1 为源点，节点 $n$ 为汇点。

子任务 5（25 分）

• $2 \leq n \leq 10^5$
• $1 \leq m \leq 2 \cdot 10^5$

翻译由 DeepSeek V3 完成