Wedding

题意翻译

题目描述: 有至多 $30$ 对夫妻将会参加一个婚宴。他们将会坐在一个长桌子的两边。 新郎新娘坐在彼此相对的一端并且新娘带着一个头饰使得她看不到和她坐在同一边的人。夫妻(也就是参加新郎新娘婚礼的人,可以理解为宾客)坐在同一边是被视为“晦气”。并且这些人中还有人是通奸关系(同性恋或者非同性恋都有可能),并且新娘同时看到任何一对中的两个人也被视为“晦气”。你的工作是去安排人们坐在桌子两边从而避免任何“晦气”。 输入: 输入由多个测试数据组成并且最后一行是 `0 0`。 每一个测试数据有一个 $n$ 表示夫妻的对数,一个 $m$ 表示通奸的对数,通奸关系的形式都是类似于:`4h 2w`(通奸关系中的两个人,一个来自第四对的丈夫,一个来自第二对的妻子)或者是 `10w 4w` 和 `3h 1h`。夫妻的编号都是从 $0$ 到 $n-1$ 编号,并且他们都是类似于 `0w 0h`。(新郎新娘的夫妻编号是 $0$) 输出: 对于每个测试数据输出一行应当与新娘坐在同一侧的人的名单,如果有多种,只用输出一种就行,如果没有则输出 `bad luck`。

题目描述

[problemUrl]: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2269 [PDF](https://uva.onlinejudge.org/external/112/p11294.pdf) ![](https://cdn.luogu.com.cn/upload/vjudge_pic/UVA11294/a184dc2d78105823fcac141994b7843124b91bc6.png)

输入输出格式

输入格式


![](https://cdn.luogu.com.cn/upload/vjudge_pic/UVA11294/841d3821248679dd689034bb3271bf5e8b8817c1.png)

输出格式


![](https://cdn.luogu.com.cn/upload/vjudge_pic/UVA11294/4a9191fdf7749cc0a395d1fd1fb465222b3ac9a2.png)

输入输出样例

输入样例 #1

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

输出样例 #1

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