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!
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.
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:
11 1 4 1 7 5 7 10 7 10 8 10 9 3 4 -1
Output 1:
1 9 7 4 11 5 8 2 10 3 6
Input 2:
3 1 2 -1
Output 2:
0
| Input 1 | Output 1 |
|---|---|
| Input 2 | Output 2 |
| Input 3 | Output 3 |
| Input 4 | Output 4 |
| Input 5 | Output 5 |