논리의 섬

논리의 섬에는 세 종류의 주민이 산다. 항상 참말만 하는 신족(divine), 항상 거짓말만 하는 악마족(evil), 그리고 낮에는 참말을, 밤에는 거짓말을 하는 인간족(human)이다. 모든 주민은 다른 모든 주민이 어떤 종족인지 알고 있다.

한 사회과학자가 이 섬을 방문하려고 한다. 겉모습만으로는 세 종족을 구별할 수 없기 때문에, 그는 주민들의 대화로부터 사실을 추론하는 대화 분석기를 만들어 달라고 부탁했다. 알아내고 싶은 사실은 지금이 낮인지 밤인지, 그리고 말을 한 각 주민이 어떤 종족인지이다.

입력은 여러 개의 대화로 이루어진다. 각 대화는 그 대화에 포함된 진술의 개수를 나타내는 정수 $n$으로 시작한다. 이어지는 $n$개의 줄에는 각각 한 주민의 진술이 하나씩 주어진다. 모든 진술 줄은 말하는 사람의 이름(대문자 A, B, C, D, E 중 하나)으로 시작하고 그 뒤에 콜론 ':'이 온다. 콜론 다음에는 아래 형식 중 하나의 진술이 온다.

• I am [not] ( divine | human | evil | lying ).
• X is [not] ( divine | human | evil | lying ).
• It is ( day | night ).

대괄호 []는 그 안의 단어가 나타날 수도, 나타나지 않을 수도 있음을 뜻하고, 소괄호 ()는 '|'로 구분된 대안 중 정확히 하나가 반드시 나타남을 뜻한다. X는 A, B, C, D, E 중 하나의 이름이다. 어떤 진술 줄에도 연속된 두 개의 공백은 없으며, 한 대화의 진술은 최대 50개이다.

입력은 첫 줄이 $n = 0$인 대화가 나오면 끝난다. 이 종료 표시는 처리하지 않는다.

각 대화에 대해, 먼저 Conversation #k 형식의 머리글 줄을 출력한다. 여기서 k는 1부터 시작하는 대화 번호이다. 그 다음, 규칙상 그 대화가 일어날 수 없다면 This is impossible.을, 어떤 사실도 추론할 수 없다면 No facts are deducible.를 출력한다. 그렇지 않으면 추론할 수 있는 모든 사실을 다음 형식으로 출력한다.

• X is ( divine | human | evil ).
• It is ( day | night ).

X는 말을 한 사람의 대문자 이름으로 바꾼다. 주민에 대한 사실을 이름의 알파벳 순서로 먼저 모두 출력한 뒤, 추론할 수 있다면 지금이 낮인지 밤인지를 출력한다. 서로 다른 대화의 출력 사이는 빈 줄 하나로 구분하며, 마지막 대화 뒤에는 빈 줄을 넣지 않는다.

이해를 돕기 위해, 어떤 주민 A가 "I am evil."이라고 말한 대화의 추론 과정을 살펴보자. A가 신족이라면 이 말은 거짓이 되므로 신족일 수 없고, 마찬가지로 A가 악마족이라면 이 말이 참이 되므로 악마족일 수도 없다. 따라서 A는 인간족이어야 하며, 지금 거짓말을 하고 있으므로 지금은 밤이어야 한다.

또 다른 예로, A가 B에 대해 서로 모순되는 두 진술(예: "B is human."과 "B is evil.")을 하는 대화를 생각해 보자. A는 분명히 거짓말을 하고 있으므로, B는 인간족도 악마족도 아니어서 신족이어야 한다. 신족 B는 항상 참말을 하므로, B의 진술 "A is evil."에 의해 A는 악마족으로 확정된다.