Свадьба
До тридцати пар будет присутствовать на свадебном банкете, на котором они будут размещены по обе стороны длинного стола. Жених и невеста сидят на одном конце стола напротив друг друга. Невеста носит искусный головной убор, который ей не позволяет видеть людей, сидящих на одной с ней стороне. Считается плохой приметой, если жених и невеста будут сидеть на одной стороне стола. Среди присутствующих существуют также пары, состоящие в родственных отношениях (как разного пола, так и одного). Считается, что невеста будет неудачливой в жизни, если она увидит обоих членов таких пар. Вам следует рассадить людей за столом так, чтобы удача всегда улыбалась невесте.
Входные данные
Входные данные состоят из нескольких тестов, за которыми следует строка, содержащая 0 0. В каждом тесте задается общее количество пар n на банкете и количество пар родственников. Далее перечислены пары родственников в виде "4h 2w" (муж из пары 4, женщина из пары 2), или "10w 4w", или "3h 1h". Присутствующие пары нумеруются числами от 0 до n-1, где невеста и жених имеют номера 0w и 0h.
Выходные данные
Для каждого теста вывести в отдельной строке список людей, которые будут сидеть на одной стороне стола вместе с невестой. Если существует несколько решений, то вывести любое. Если решения не существует, то вывести строку, содержащую "bad luck".