3646. [POJ 3648]婚礼

【题目描述】

很多对（不超过 30）夫妇将参加婚礼盛宴，他们将坐在长桌的两侧。

新娘和新郎坐在一端，彼此相对，新娘戴着精致的头饰，使她看不到与她在同一侧的人。

安排丈夫和妻子坐在桌子的同一侧是不幸的。

此外，新娘知道有几对人之间有矛盾（性别不限），并且新娘看到这样的一对成员是不幸的。

你的工作是安排人们的位置，以避免不幸。

【输入格式】

输入包含多组测试用例。

每组测试用例，第一行包含两个整数 $n$ 和$ m$，表示共有 $n$ 对夫妇，$m$ 对有矛盾的人。

接下来 $m$ 行，每行表示一对有矛盾的人。

形如 4h 2w 表示第 4 对夫妇中的丈夫和第 2 对夫妇中的妻子有矛盾，3h 1h 表示第 3 对夫妇中的丈夫和第 1 对夫妇中的丈夫有矛盾。

每对夫妇被编号为 $0,1,\cdots,n-1$，其中新郎新娘的编号为 $0$。

当输入一行为 0 0 时，表示输入终止。

【输出格式】

每组测试用例输出一个结果，每个结果占一行。

结果包含同新娘坐在一侧的人员列表。

如果有多种方案，随便输出一种即可。

输出结果时，请按照编号从小到大（即 $1\sim n-1$）的顺序，输出人员。

如果没有方案，则输出bad luck。

【样例输入】

10 6
3h 7h
5w 3w
7h 6w
8w 3w
7h 3w
2w 5h
0 0

【样例输出】

1h 2h 3w 4h 5h 6h 7h 8h 9h