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

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

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

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

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

输入格式

输入包含多组测试用例。

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

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

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

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

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

输出格式

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

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

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

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