Island of Logic

Interview

Time limit1sMemory limit128 MB

Summary

Given statements by islanders who always tell the truth, always lie, or lie only at night, deduce every fact forced across all valid assignments.

Level: Medium6 of 10
Topics: Brute force, Simulation, Implementation, Math
Solved: No attempts yet

Problem

The Island of Logic is home to three kinds of inhabitants: divine beings that always tell the truth, evil beings that always lie, and human beings that are truthful during the day and lie at night. Every inhabitant knows the type of every other inhabitant.

A social scientist wants to visit the island. Because he cannot tell the three kinds apart from their looks alone, he asks you for a conversation analyzer that deduces facts from the inhabitants' conversations. The facts of interest are whether it is day or night and what kind of being each speaker is.

Input

The input contains several conversations. Each conversation starts with an integer $n$ , the number of statements in it. The next $n$ lines each contain one statement by an inhabitant. Every statement line begins with the speaker's name, one of the capital letters A, B, C, D, E, followed by a colon ':'. After the colon comes one of the following kinds of statements:

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

Square brackets [] mean the enclosed word may or may not appear; round brackets () mean exactly one of the alternatives separated by '|' must appear. X stands for one of the names A, B, C, D, E. No statement line contains two consecutive spaces, and a conversation has at most 50 statements.

The input ends with a conversation whose first line is $n = 0$ ; this terminator is not processed.

Output

For each conversation, first print a header line Conversation #k, where k is the 1-based number of the conversation. Then, if the conversation cannot happen under the rules, print This is impossible.; if no fact can be deduced, print No facts are deducible.. Otherwise print every fact that can be deduced, using these formats:

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

X is replaced by the capital-letter name of a speaker. Facts about inhabitants come first, in alphabetical order of their names; then, if it can be deduced, whether it is day or night. Separate the output of consecutive conversations with a single blank line; there is no trailing blank line after the last conversation.

Hint

To make the idea clearer, consider the sample conversation in which A says "I am evil." What can be deduced? A cannot be divine, because then the statement would be a lie; likewise A cannot be evil, because then it would be the truth. Therefore A must be human, and since A is lying it must be night.

Consider another sample conversation in which A makes two contradictory claims about B (for example "B is human." and "B is evil."). A is clearly lying, so B can be neither human nor evil and must therefore be divine. Because B always tells the truth, B's statement "A is evil." forces A to be evil.

Examples1

Example 1

Input

1
A: I am divine.
1
A: I am lying.
1
A: I am evil.
3
A: B is human.
B: A is evil.
A: B is evil.
0

Expected output

Conversation #1
No facts are deducible.

Conversation #2
This is impossible.

Conversation #3
A is human.
It is night.

Conversation #4
A is evil.
B is divine.