P1039 [NOIP 2003 Senior] Detective Reasoning

Mingming has recently become obsessed with the detective manga "Conan" and is immersed in deduction games, so he gathered a group of classmates to play a reasoning game. The game goes like this: Mingming's classmates agree in advance that one of them will act as the criminal (without Mingming knowing). Mingming's task is to find out who the criminal is. Then Mingming asks each classmate one by one, and the respondent may say: $$ \def\arraystretch{1.5} \begin{array}{|l|l|}\hline \textbf{\textsf{Statement Content}} & \textbf{\textsf{Meaning of the Statement}}\\\hline \text{I am guilty.} & \text{I am the criminal.} \\\hline \text{I am not guilty.} & \text{I am not the criminal.} \\\hline \text{{\tt XXX} is guilty.} & \text{{\tt XXX} is the criminal. Here, {\tt XXX} denotes a student's name.} \\\hline \text{{\tt XXX} is not guilty.} & \text{{\tt XXX} is not the criminal.} \\\hline \text{Today is {\tt XXX}.} & \begin{aligned} &\text{Today is {\tt XXX}. Here, {\tt XXX} denotes a day of the week.}\\ &\text{The day of the week can only be one of the following:}\\ &\texttt{Monday}, \texttt{Tuesday}, \texttt{Wednesday}, \texttt{Thursday}, \\ &\texttt{Friday}, \texttt{Saturday}, \texttt{Sunday}. \end{aligned} \\\hline \end{array}$$ Any other words that appear in the statements are not included in the logical reasoning. What Mingming knows is that among his classmates, there are $N$ people who always lie, and the rest always tell the truth. Now Mingming needs you to help him deduce from his classmates' statements who the real criminal is. Remember, there is exactly one criminal!

The input consists of multiple lines. The first line contains three integers, $M$, $N$, and $P$. $M$ is the number of Mingming's classmates participating in the game, $N$ is the number of people who always lie, and $P$ is the total number of statements. The next $M$ lines each contain the name of one of Mingming's classmates (composed of English letters, no spaces, all uppercase). Then there are $P$ lines. Each line starts with a classmate's name, immediately followed by a colon and a space, and then a single statement that matches one of the formats listed in the table above. Each statement line will not exceed 250 characters. The input will not contain two consecutive spaces, and there are no leading or trailing spaces on any line.

If your program can determine who the criminal is, output his name. If the program determines that more than one person could be the criminal, output `Cannot Determine`. If the program determines that no one could be the criminal, output `Impossible`.

For 100% of the testdata, $1 \le M \le 20$, $0 \le N \le M$, $1 \le P \le 100$. Source: NOIP 2003 Senior, Problem 2. Translated by ChatGPT 5