1548 . 尋找邪惡的根源!!!
TopCoder
Description
初極狹，纔通人；復行數十步，豁然開朗。土地平曠，屋舍儼然。有良田、美池、桑、竹之屬，阡陌交通，雞犬相聞。其中往來種作，男女衣著，悉如外人；黃髮垂髫，並佁然自樂。見漁人，乃大驚，問所從來；具答之。便要還家，設酒、殺雞、作食。村中聞有此人，咸來問訊。自云：「先世避秦時亂，率妻子邑人來此絕境，不復出焉；遂與外人間隔。」問「今是何世？」乃不知有漢，無論魏、晉！此人一一為具言所聞，皆歎惋。餘人各復延至其家，皆出酒食。停數日，辭去。此中人語云：「不足為外人道也。」 ---- 陶淵明《桃花源記》
快樂國的快樂村，原本是個和平安詳的小村子，快樂辛勤的工作，與外界隔閡，自給自足，和平共存，相親相愛>///<，過著無憂無慮的生活。
直到有一天..，黑暗降臨了，大家閉上眼睛，準備開始玩殺手?，阿...是準備睡覺。
一個邪惡的靈體隨著祭壇的被閃電破壞，而放出了......。
據說這個邪惡的靈體，是一個叫做十甫寸邪靈神的家伙，經由上一代的大祭司犧牲自己而封印起來的。
而這個十甫寸邪靈神，將會附著在某個村民的身上，使這個他變非常的邪惡(evil)。
經過幾日的觀察，雖然看似沒什麼差別，不過大家漸漸的都已經有了共識，知道哪個人是邪惡的。
但不敢說出來的原因是，怕因此和譪可親的大祭司會因此而必須犧牲生命。
因此在大家都不肯招供的情況下，大祭司找到了n位感覺有可能是被邪惡的惡靈，決定詢問這些人一些問題來找出邪靈神。
不過同樣的，有些人因為害怕這位被附身的好朋友會因此而死亡，有些人則因為怕大祭司會因此而犧牲，所以有些人決定說謊，或者是逃避問題。
每個人說話主要有以下幾種可能：
- I am evil.
- I am not evil.
- XXX is evil. ：其中XXX代表某人名字。
- XXX is not evil. ：其中XXX代表某人名字。
- Today is XXX. ：其中XXX代表今天星期幾(Monday, Tuesday, Wednesday, Thursday, Friday, Saturday, Sunday)。
- 其他不相關的廢話
而經由大祭司的占卜，他可以得知總共會有m個人說謊，而說謊跟邪不邪惡其實沒有太大的關係。
且說謊的人一定說謊，誠實的人一定誠實。
也就是對同一個人來說不會有一些話是真的一些話是假的情況，要馬全都真的，要馬全都假的。
請問你是否有辦法幫大祭司找出，哪一位是邪惡的邪靈神呢??
Input Format
輸入包含三個數n,m,q(1<=m<=n<=20，1<=q<=1000)。
接下來有n行，代表這n個人的名字。(每個人的名字長度<=100，且僅會有大小寫英文字母或數字)
而第n+1到第n+q+1行，一行代表一個對話，代表q個對話，對話說出的方式是：
「某人:□要說的話」(□代表一個半形空白，且這個某人的名字一定在前面出現過，要說的話長度<=150)。
※要注意的是，大小寫都一定要與上述前五種話符合，才具有實質意義，且字與字之間會有且僅有一個半形空白。
Output Format
如果你能確定誰是邪靈神，則輸出他的名字。
如果你判斷出不止一個人可能是邪靈神，且又與大家的話都沒矛盾，則輸出＂Cannot Determine＂(不包含雙引號)。
否則輸出＂Impossible＂。
Sample Input 1
surwkgod
skumallo2
lolifarmer
fatsky
surwkgod: I am evil.
skumallo2: Yes, you are evil.
lolifarmer: I am evil!
surwkgod: fatsky how way@@!
surwkgod: I love hotdog!!
fatsky: ring ring, hello~?
surwkgod: Today is Saturday.
surwkgod: Today is sunday.
skumallo2: surwkgod is evil.
lolifarmer: I love Lolis(>///<).
lolifarmer: cho-ka-cho-ka-cho-ka, shoe~shoe~~~
Sample Output 1
Hints
※2009/7/24補充敘述by math120908
Problem Source
原TIOJ1548 / Problem Setter: math120908
( Adapt from Noip2003 提高組 -- 侦探推理 )
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0 | 6 |
| 2 | 1 | 6 |
| 3 | 2 | 6 |
| 4 | 3 | 6 |
| 5 | 4 | 6 |
| 6 | 5 | 6 |
| 7 | 6 | 6 |
| 8 | 7 | 6 |
| 9 | 8 | 6 |
| 10 | 9 | 6 |
| 11 | 10 | 6 |
| 12 | 11 | 6 |
| 13 | 12 | 6 |
| 14 | 13 | 6 |
| 15 | 14 | 16 |