거짓말쟁이

로빈슨 크루소가 탄 배는 폭풍우에 난파되었고, 그는 우여곡절 끝에 혼자서 한 섬에 도착하게 되었다. 그는 지치고 절망하였지만 불행 중 다행으로 어릴 때 들은 도착한 섬에 대한 전설을 아직도 생생히 기억할 수 있었다. 그 전설에 따르면 섬에는 선한 사람으로 구성된 종족과 악한 사람으로 구성된 종족이 살고 있다. 그는 살아남기 위해서 선한 종족과 악한 종족을 구별할 필요가 생겼는데, 그것이 그리 쉽지는 않았다. 사람들의 외모는 너무 비슷하여 그것으로 구별할 수 없었다.

아직도 희망이 완전히 사라진 것은 아니다. 그는 기억 속에서 다음과 같이 유용한 정보를 끄집어낼 수 있었다. 그 섬에 사는 사람들은 모두 서로 잘 알고 있어서, 각자는 어떤 사람이 선한 종족이고 어떤 사람이 악한 종족인지를 구별할 수 있다. 악한 종족 사람들은 자기 마음에 드는 질문에는 대답을 하지만, 그렇지 않으면 질문한 사람을 저주하여 죽일 수도 있다. 다행히도 어떤 사람에게 다른 사람이 선한 종족인지 아닌지를 묻는 질문은 악한 종족의 비위를 거스르는 것이 아니고 따라서 그 질문은 안전하다. 선한 종족 사람들은 모두 항상 참말만 하는 참말쟁이이고, 악한 종족 사람들은 모두 항상 거짓말만 하는 거짓말쟁이이다. 두 종족 사람의 수가 전설에 나와 있어서 미리 알고 있고, 수세기 동안 그 수는 변하지 않고 있다.

로빈슨 크루소가 당신에게 도움을 청해왔다. 당신이 할 일은 그를 도와서 그의 질문에 대한 사람들의 대답을 보고 어떤 사람이 선한 종족이고 어떤 사람이 악한 종족인가를 알아내는 프로그램을 작성하는 것이다. 프로그램 이름은 liar.cpp, 프로그램 설명 파일 이름은 liar.hwp로 하고, 실행 시간은 1초를 초과할 수 없다. 부분 점수는 없다.

입력 형식

입력 파일의 이름은 input.txt이다. 첫 줄에는 세 정수 [eqn: n], [eqn: p_1], [eqn: p_2]가 입력된다. [eqn: n]은 로빈슨 크루소가 물은 질문의 수이고, [eqn: p_1], [eqn: p_2]는 각각 선한 종족과 악한 종족 사람의 수이다. 그 후 [eqn: n]개의 줄 각각은 두 정수 [eqn: x_i], [eqn: y_i]와 한 단어 [eqn: a_i]가 입력된다. [eqn: x_i]와 [eqn: y_i]는 섬에 사는 사람의 번호이다. 섬에 사는 사람은 [eqn: 1]부터 [eqn: p_1 + p_2]까지 미리 번호가 매겨져 있다. [eqn: a_i]는 yes이거나 no인데, [eqn: x_i]가 말하기를 [eqn: y_i]가 선한 종족 사람이라고 했다면 yes이고 그렇지 않으면 no이다. [eqn: x_i]와 [eqn: y_i]는 같은 사람일 수 도 있다. 왜냐하면, ‘당신은 선한 종족 사람이냐?’라고 물을 수 있기 때문이다. 서로 다른 두 줄에 있는 [eqn: x_i]와 [eqn: y_i], 그리고 [eqn: x_j]와 [eqn: y_j]가 서로 같을 수도 있는데, 그것은 로빈슨 크루소가 흥분하여 같은 사람에게 같은 질문을 했을 수 있기 때문이다. [eqn: n]은 1000 이하이고, [eqn: p_1]과 [eqn: p_2]는 모두 300 이하이다.

2003 가을학기 문제해결기법	문제 #4

출력 형식

출력 파일의 이름은 output.txt이다. 섬에 사는 사람을 모두 선한 종족과 악한 종족으로 분류할 만큼 충분한 정보가 주어져 있으면, 첫째 줄에 선한 종족 사람의 번호를 오름차순으로 출력하고, 그렇지 않으면 첫 줄에 그냥 ‘NO’라고 출력한다.

입력과 출력의 예

입력(input.txt)

2 2 1

1 2 yes

2 3 no

출력(output.txt)

1 2