Wedding#6675
Up to thirty couples will attend a wedding feast, seated on either side of a long table. The bride and groom sit at one end, opposite each other; the bride wears an elaborate headdress, which prevents her from seeing anyone seated on the same side of the table as herself. It is considered bad luck if a husband and wife are seated on the same side of the table. Additionally, some pairs of people are known to be in forbidden relationships (which can be between any two people, regardless of gender). It is also considered bad luck if the bride can see both members of such a pair (i.e., if both are seated on the side opposite her).
You are to find a way to seat everyone at the table so that none of these bad luck conditions occur.
The input consists of several test cases, followed by a line containing 0 0. Each test case begins with the integer , the number of couples, followed by the number of forbidden pairs, then by that many descriptions of forbidden pairs. Each pair is specified in the form "4h 2w" (the husband from couple 4, the wife from couple 2), or "10w 4w", or "3h 1h", etc. Couples are numbered from to n-1, with the bride and groom being 0w and 0h respectively.
For each test case, output a single line listing the people who must be seated on the same side as the bride. If multiple solutions are possible, output any one of them. If no valid arrangement exists, output a single line containing bad luck.
Example 1