题目描述

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

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

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

此外，有几对人进行通奸关系（不同性别和同性关系都是可能的），并且新娘看到这样的一对成员是不幸的。

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

输入格式

输入包含多组测试用例。

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

接下来 $m$ 行，每行揭露一个通奸关系。

形如 4h 2w 表示第 $4$ 对夫妇中的丈夫和第 $2$ 对夫妇中的妻子通奸，3h 1h 表示第 $3$ 对夫妇中的丈夫和第 $1$ 对夫妇中的丈夫通奸。

每对夫妇被编号为 $0,1,\dots,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

样例解释

有 $10$ 对夫妇（编号 $0$ 到 $9$，$0$ 是新郎新娘），$6$ 条通奸关系。

需要输出与新娘在同一侧的人（新娘在左侧，新郎在右侧，新娘只能看见对面，因此和她同侧的人她看不见）。

输出给出了编号从 $1$ 到 $9$ 的人员列表，其中带 h 表示丈夫，带 w 表示妻子。

数据范围

• 夫妇对数 $n$ 满足 $n \le 30$
• 通奸关系数 $m$ 未给出明确上限，但输入规模合理
• 多组测试用例，以 0 0 结束

时空限制

• 时间限制：1 秒
• 空间限制：64 MB