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

**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*.

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.

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.

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.

1 5 3 4 7 2 6

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.

Meeting cancelled.

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-2021

Page generated: 1 December 2021, 10:37am AEDT