You are given an undirected connected graph that has nodes. The nodes are numbered .
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 to node , node is before node 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.
输入格式
The first line has two integers and : the number of nodes and edges.
After this, there are lines that describe the edges. Each line has two integers and : there is an edge between nodes and .
It is guaranteed that the graph is connected, contains no self-loops and there is at most one edge between every pair of nodes.
输出格式
Print any valid ordering of the nodes. If there are no solutions, print "IMPOSSIBLE".
样例
样例输入 1
5 5
4 2
3 4
2 1
3 1
1 5
样例输出 1
4 2 3 1 5
样例输入 2
4 3
1 2
3 2
4 2
样例输出 2
IMPOSSIBLE
数据范围与提示
Subtask 1 (7 points)
The graph is a tree.
Subtask 2 (29 points)
Subtask 3 (18 points)
Subtask 4 (21 points)
It is guaranteed that there exists a valid ordering with node 1 as the source, and node as the sink.
