- Time limit: 1.00 s
- Memory limit: 512 MB
Let us consider an ordering of the nodes. The first node in the ordering is called the source, and the last node is called the sink. In addition, a path is called valid if always when we move from node $a$ to node $b$, node $a$ is before node $b$ in the ordering.
Your task is to find an ordering such that (1) there is a valid path from the source to every node, and (2) there is a valid path from every node to the sink, or determine that it is not possible to create such an ordering.
Input
The first line has two integers $n$ and $m$: the number of nodes and edges.
After this, there are $m$ lines that describe the edges. Each line has two integers $a$ and $b$: there is an edge between nodes $a$ and $b$.
It is guaranteed that the graph is connected, contains no self-loops and there is at most one edge between every pair of nodes.
Output
Print any valid ordering of the nodes. If there are no solutions, print "IMPOSSIBLE".
Example 1
Input:
5 5
4 2
3 4
2 1
3 1
1 5
Output:
4 2 3 1 5
Example 2
Input:
4 3
1 2
3 2
4 2
Output:
IMPOSSIBLE
Subtask 1 (7 points)
- $2 \le n \le 10^{5}$
- The graph is a tree.
- $2 \le n \le 100$
- $1 \le m \le 200$
- $2 \le n \le 2000$
- $1 \le m \le 5000$
- $2 \le n \le 10^{5}$
- $1 \le m \le 2 \cdot 10^{5}$
- It is guaranteed that there exists a valid ordering with node 1 as the source, and node $n$ as the sink.
- $2 \le n \le 10^{5}$
- $1 \le m \le 2 \cdot 10^{5}$