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