该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

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

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

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

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

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

输入格式

输入包含多组测试用例。

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

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

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

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

当输入一行为$\red {0~ 0}$时，表示输入终止。

输出格式

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

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

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

输出结果时，请按照编号从小到大（即$\red {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