사랑과 전쟁

철승이와 그의 아내 보람이가 여러 부부가 모이는 파티에 참석했다. 파티에는 모두 $N$쌍의 부부가 참가한다. 긴 테이블의 양쪽에는 각각 $N$개씩 모두 $2N$개의 의자가 놓여 있고, 한 의자에는 한 사람만 앉을 수 있다.

파티 참가자는 0h, 0w, 1h, 1w, $\dots$, (N-1)h, (N-1)w로 나타낸다. 여기서 kh는 $k$번째 부부의 남편, kw는 $k$번째 부부의 아내를 뜻한다. 0번째 부부는 항상 철승이(0h)와 보람이(0w)이다.

이 파티에는 한 부부의 남편과 아내는 반드시 서로 다른 쪽(마주 보는 방향)에 앉아야 한다는 규칙이 있다. 결혼기념일을 맞은 철승이와 보람이는 각자 자기 쪽 맨 앞자리에 마주 보고 앉았다. 즉 철승이는 '철승이 쪽'에, 보람이는 '보람이 쪽'에 앉는다.

철승이는 참가자들 사이에 여러 불륜 관계가 있다는 사실을 알게 되었다. 순수한 보람이가 불륜 관계인 사람들을 함께 보지 않도록, 철승이는 사람들의 자리를 직접 정하기로 했다. 보람이는 오직 철승이 쪽만 바라보므로, 철승이 쪽에는 서로 불륜 관계인 두 사람이 동시에 앉아서는 안 된다. (보람이 쪽에는 이러한 제한이 없다.)

정리하면, 다음 두 조건을 모두 만족하도록 각 사람을 어느 쪽에 앉힐지 정해야 한다.

• 모든 부부는 남편과 아내가 서로 반대쪽에 앉는다.
• 철승이 쪽에는 서로 불륜 관계인 두 사람이 동시에 앉지 않는다.

입력은 여러 개의 테스트 케이스로 이루어진다.

각 테스트 케이스의 첫 줄에는 부부의 수 $N$과 불륜 관계의 수 $M$이 주어진다. ($1 \le N \le 30$, $0 \le M \le 50$)

이어지는 $M$개의 줄에는 불륜 관계인 두 사람이 주어진다. 예를 들어 4h 2w는 4번째 부부의 남편과 2번째 부부의 아내가 불륜 관계라는 뜻이다. 각 부부는 이성 부부이지만, 불륜 관계는 동성 사이에서도 존재할 수 있다. 0h와 0w는 항상 철승이와 보람이를 나타낸다.

$N$과 $M$이 모두 0으로 주어지면(0 0) 입력이 끝난다.

각 테스트 케이스마다, 조건을 만족하는 자리 배치에서 보람이 쪽에 앉는 사람들을 한 줄에 출력한다. 1번째 부부부터 $N-1$번째 부부까지 부부 번호가 작은 것부터 차례로, 각 부부에서 보람이 쪽에 앉는 한 사람을 공백으로 구분하여 출력한다. (0번째 부부의 보람이 0w는 출력하지 않는다.)

조건을 만족하는 배치가 여러 가지일 수 있다. 이때에는 사전순으로 가장 앞서는 출력만을 하나 선택하여 출력한다. 각 부부에서 남편을 나타내는 토큰 kh는 아내를 나타내는 토큰 kw보다 사전순으로 앞선다고 본다. 즉 부부 번호가 작은 쪽부터 차례로, 유효한 배치가 존재하는 한 남편 kh를 보람이 쪽에 두는 것을 우선한다.

조건을 만족하는 배치가 하나도 존재하지 않으면 bad luck을 출력한다.