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