사랑과 전쟁

철승이와 그의 아내인 보람이는 여러 부부가 모이는 파티에 참가했습니다. 이 파티에는 총 N커플이 참가합니다. 파티장에는 긴 테이블의 양 쪽에 참가자들이 앉을 의자가 N개씩, 총 2N개의 의자가 놓아져 있으며 한 의자에는 한 명만 앉을 수 있습니다. 파티에 참가한 사람은 0h, 0w, 1h, 1w, ... , (N-1)h, (N-1)w로 표현되며 kh는 k번째 커플의 남편, kw는 k번째 커플의 아내를 나타냅니다. 이때 0번째 커플은 항상 철승이와 보람이입니다.

오늘이 결혼 기념일이었던 철승이와 보람이는 서로 양쪽 첫 번째 줄에 앉게 되었습니다. 이 파티에는 아내와 남편은 같은 방향의 줄에 앉을 수 없다는 규칙이 있습니다. 즉, 부부는 서로 마주보는 방향으로 앉아야만 합니다.

평소 어둠의 커뮤니티 고동넷의 회원이던 철승이는 이 파티에 자주 보던 얼굴들이 있는 것을 발견했고, 한 사람의 귀띔으로 이 부부들 사이에는 수 많은 불륜 관계가 있다는 것을 알게 되었습니다. 철승이는 이런 불륜 커플들을 순수한 보람이가 보면 안 된다고 생각하고, 갑자기 자신이 사람들의 자리를 정해주기로 했습니다.

• 이 파티의 규칙대로 한 부부의 남편과 아내는 서로 반대편에 앉아야 합니다.
• 순수하고 낯을 많이 가리는 보람이는 철승이쪽만을 바라봅니다. 그래서 철승이가 앉은 줄에 불륜 관계인 두 사람이 앉을 수 없습니다.

철승이가 사람들의 자리를 배치하는 것을 도와줍시다. 어떤 사람들이 보람이와 같은 방향에 앉아야 할 지 정해야 합니다.

입력은 여러 테스트 케이스로 구성되어있다.

각 테스트 케이스의 첫 줄에는 커플의 수 N과, 불륜 관계의 수 M이 주어진다. (N ≤ 30, M ≤ 50)

그 후 M줄에 걸쳐 불륜 관계를 이루는 두 사람의 번호가 주어진다. 예를 들어 "4h 2w"는 4번째 커플의 남편과 두 번째 커플의 아내가 불륜 관계라는 의미이다. 각 부부는 서로 이성이지만, 불륜 관계는 동성간에도 일어날 수 있음에 주의하라. 단 0h, 0w는 무조건 철승이와 보람이를 나타낸다.

N과 M이 0 0으로 주어지면 프로그램을 종료한다.

각 테스트 케이스 별로 조건들을 만족하였을 때 보람이 쪽에 앉아야하는 사람들의 번호를 오름차순으로 출력하시오. 조건을 만족하는 배치가 여러 가지 있을 수 있으므로, 그 중 하나만 출력하면 된다. 만약 해당 테스트 케이스에 답이 존재할 수 없다면, "bad luck"을 출력한다.