AIOC Banner

Problem: King Arthur

Want to try solving this problem? You can submit your code online if you log in or register.


King Arthur

Input File: arthin.txt
Output File: arthout.txt
Time Limit: 0.2 seconds

King Arthur has a problem. The knights of the round table meet regularly to discuss which dragons need slaying and which grails need recovering.

When organizing the next such meeting, Galahad approached Arthur and asked not to be seated next to Lancelot at the next meeting. Arthur asked Lancelot if he could explain Galahad's request, and Lancelot admitted to playing a rather successful joke on Galahad, which had led to a falling out. Soon after, Balin approached and asked to be seated next to Galahad, having heard of Galahad's plight and being sworn to assist him. While pondering these requests, Arthur remembered that Macbeth was visiting from Scotland, and protocol demanded that Macbeth be seated next to Arthur as king.

Arthur approached Merlin for help, and Merlin decided that it would be best to employ a computer programmer to solve such seating problems for once and for all. So you have been called in to save Camelot from disarray.

To assist you, Merlin has numbered the knights at the meeting from 1 to n, and numbered the seats at the table from 1 to n in order around the table. Arthur is knight 1, and must be seated in seat 1. Provided you honour each request to sit apart or together, all will be well. Note that the table is round - seat 1 is next to seats 2 and n.

Input

The first line consists of a single integer n, the number of people at the round table meeting. You may assume 2 <= n <= 12.

Following this are zero or more lines each containing a pair of positive integers c d, separated by a single space, giving the numbers of two knights who must be seated next to each other. You may assume that 1 <= c <= n, that 1 <= d <= n, and that c is not equal to d. This section is terminated by a line consisting of a pair of zeros separated by a single space - i.e., 0 0.

Following this are zero or more lines each containing a pair of positive integers a b, giving the numbers of two knights who may not be seated next to each other. You may assume that 1 <= a <= n, that 1 <= b <= n, and that a is not equal to b. This section is also terminated by a line consisting of a pair of zeros separated by a single space - i.e., 0 0.

Output

If it is possible to honour all the requests, your program shall output a single line of output containing n positive integers separated by spaces. The first integer is the number of the knight in seat 1, the second is the number of the knight in seat 2, and so on. Each number from 1 to n inclusive must appear exactly once.

If it is not possible to honour all the requests, your program shall output the single line

Meeting cancelled.

Note that in the case that all requests can be honoured, there may be many ways to seat the knights. Your program may output any single seating that satisfies all the requests.

Sample Input 1

7
1 5
3 4
1 6
0 0
2 3
2 4
0 0

There are seven knights. The first and fifth must be seated adjacent, the first and sixth must be seated adjacent, and the third and fourth must be seated adjacent. The second and third may not be seated adjacent, and the second and fourth may not be seated adjacent.

Sample Output 1

1 5 3 4 7 2 6

Sample Input 2

5
5 1
3 4
0 0
2 3
4 2
0 0

There are five knights. The first and fifth must be seated adjacent, and the third and fourth must be seated adjacent. The second and third may not be seated adjacent, and the second and fourth may not be seated adjacent.

Sample Output 2

Meeting cancelled.

Scoring

Your program will receive 100% for providing a correct seating in the event that one exists, or correctly deciding that no such seating exists. All other results shall be worth 0%.

 


Privacy statement
© Australian Mathematics Trust 2001-2019

Contact: training@orac.amt.edu.au
Page generated: 24 May 2019,  4:07am AEST