CEOI 96 Day 2 Problem 3
The electrician Fero has just finished the installation of the new cable in the building of the CEOI secretariat. The cable consists of N wires and connects the computer room and CEOI secretary office. In the computer room Fero labeled the wires with numbers from 1 to N from left to right. Because the cable was long, sometimes some of wires crossed between the computer room and the office (each pair of wires crosses at most once; at each moment only neighbouring wires may cross). So in the office the wires were not ordered the same way (see figure 1).
To know how these wires are crossed Fero drew the graph on the wall near the cable end in the computer room. The vertices represented wires and edges represented wire crosses. There is an edge between vertices a and b if and only if the wires a and b are crossed somewhere on the way (see figure 2 for graph representing situation in figure 1).
The cable does not function properly now. Unfortunately Fero broke his leg yesterday. We have another electrician but he is not so experienced in graph theory. He needs to know the order of wires at the end of the cable in the CEOI secretary office to correct this fault.
In the input file there are several blocks of data. The first line of each block contains two numbers N and M separated by a space, where N (1 <= N <= 100) is the number of wires in the cable and M is the number of wire crosses. This is followed by M lines each containing pair of integers A, B separated by a space (1 <= A,B <= N) representing the cross of cable wires A and B somewhere on the way. After the last block there is a line with two numbers 0.
For each block of the input file the output file contains a single line with the list of wire numbers in order as they appear at the second end of the cable (N numbers separated by space) or the message "IMPOSSIBLE" if no order is represented by given graph.
5 4 1 2 1 3 2 3 1 4 0 0
3 2 4 1 5