시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 696 | 143 | 92 | 17.726% |
철승이와 그의 아내인 보람이는 여러 부부가 모이는 파티에 참가했습니다. 이 파티에는 총 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"을 출력한다.
10 6 3h 7h 5w 3w 7h 6w 8w 3w 7h 3w 2w 5h 0 0
1h 2h 3w 4h 5h 6h 7h 8h 9h