next up previous
Next: Quaternion Calculator Up: No Title Previous: Line Drawing

Seating Diplomats

As the Secretary General of the United Nations, you are responsible for keeping everyone in the world relatively happy with each other and avoiding friction as much as possible. Since the United Nations has a lot of conferences which involve eating, you must seat all the ambassadors around a circular table without seating people in such a way that political friction might spring up. Your staff gives you a list of how many ambassadors there are and who must not be seated next to whom.

In order to make sure your decisions are foolproof, you write a program which you figure to be faultless to figure out the seating arrangements for you. Good luck with your conference and remember - the fate of the world is in your hands!

Input Format

The input will first consist of a line containing the total number of diplomats, followed by lines containing pairs of diplomats who must NOT be seated together. The list will be terminated by a line containing only -1.

Output Format

The output should be a sequence of numbers representing one possible correct seating of the diplomats (based on the input). The diplomats must be numbered from 1 to N (where N is the total number of diplomats given in the input). If no seating arrangement is possible, the program prints a 0 (zero).


Input 1:

1 4
1 7
5 7
10 7
10 8
10 9
3 4

Output 1:

1 9 7 4 11 5 8 2 10 3 6

Input 2:

1 2

Output 2:


Test data used in judging

Input 1 Output 1
Input 2 Output 2
Input 3 Output 3
Input 4 Output 4
Input 5 Output 5

Our Solution

Chau-Wen Tseng
Mon Mar 15 13:58:05 EST 1999