← 返回题目列表

Codeforces · 156/B

B. 嫌疑人

中文机器翻译题面 查看原题

当夏洛克·福尔摩斯调查犯罪时,他确定了 n 名嫌疑人。他确信正是他们中的一个人犯下了罪行。为了找出是谁干的,侦探将嫌疑人排成一排,并从 1 到 n 编号。随后,他逐一询问:“哪一个犯了罪?”。犯罪嫌疑人i号要么回答“犯罪嫌疑人ai号犯罪”,要么回答“犯罪嫌疑人ai号没有犯罪”。此外,嫌疑人也可以这样描述自己 (ai = i)。

夏洛克·福尔摩斯确信 m 个答案是真实的,而所有其他答案都是谎言。现在帮助他理解这一点:哪个嫌疑人撒谎,哪个嫌疑人说真话?

输入

第一行包含两个整数 n 和 m (1 ≤ n ≤ 105, 0 ≤ m ≤ n)——嫌疑人总数和说真话的嫌疑人数量。接下来的 n 行包含嫌疑人的答案。第 i 行包含“+ai”(不带引号),如果犯罪嫌疑人 i 表示犯罪嫌疑人 ai 实施犯罪,或者包含“-ai”(不带引号),如果犯罪嫌疑人 i 表示犯罪嫌疑人 ai 没有实施犯罪(ai 是整数,1 ≤ ai ≤ n)。

保证至少有一名嫌疑人存在,这样如果他犯了罪,那么恰好有 m 个人说出了真相。

输出

打印 n 行。如果嫌疑人 i 确实说出了真相,那么行号 i 应该包含“真相”。如果嫌疑人确实撒了谎,则打印“Lie”;如果他可以撒谎并且也可以说实话,则打印“Not Define”,具体取决于犯罪者。

示例

输入 #1

1 1
+1

输出 #1

Truth

输入 #2

3 2
-1
-2
-3

输出 #2

Not defined
Not defined
Not defined

输入 #3

4 1
+2
-3
+4
-1

输出 #3

Lie
Not defined
Lie
Not defined

注意

第一个样本只有一个人,他承认了罪行,夏洛克·福尔摩斯知道一个人说的是实话。这说明这个人说的是实话。

在第二个样本中,有三名嫌疑人,每个人都否认自己有罪。夏洛克·福尔摩斯知道他们中只有两个人说的是实话。他们中的任何一个人都可能是罪犯,所以我们不知道他们中的任何一个人是否说的是真话。

在第三个样本中,第二个和第四个嫌疑人为第一个和第三个嫌疑人辩护。但只有一个人说的是实话,因此,第一个或第三个就是罪犯。他们俩都可能是罪犯,所以第二个和第四个要么在说谎,要么说实话。第一个和第三个肯定是在撒谎,因为他们在指责第二个和第四个。