CF156B Suspects

当福尔摩斯正在侦破一起案件时，他确定有 $n$ 名嫌疑人。他确信其中恰好有一人犯下了罪行。为了找出罪犯是谁，侦探让嫌疑人排成一队，并将他们编号为 $1$ 到 $n$。随后，他向每个人提问：“是谁犯下了罪行？”编号为 $i$ 的嫌疑人要么回答 “罪犯是编号为 $a_i$ 的嫌疑人”，要么回答 “编号为 $a_i$ 的嫌疑人没有犯下罪行”。嫌疑人也可以这么说自己（即 $a_i = i$）。 福尔摩斯非常确定，恰好有 $m$ 个答案是实话，其余的都是谎言。现在请你判断：每位嫌疑人一定在说实话、一定在撒谎，还是也有可能说真话也有可能说谎？

第一行包含两个整数 $n$ 和 $m$（$1 \le n \le 10^5, 0 \le m \le n$）——嫌疑人的总数和说实话的人数。接下来的 $n$ 行为每个嫌疑人的回答。第 $i$ 行包含 "+ $a_i$"（不带引号），表示第 $i$ 个人说罪犯是编号为 $a_i$ 的人；或者包含 "- $a_i$"（不带引号），表示第 $i$ 个人说编号为 $a_i$ 的人没有犯下罪行（$a_i$ 是一个整数，$1 \le a_i \le n$）。 保证至少存在一种嫌疑人是罪犯时，恰好有 $m$ 个回答为真的方案。

输出 $n$ 行。第 $i$ 行如果可以确定第 $i$ 个人一定在说实话，输出 “Truth”；如果一定在说谎，输出 “Lie”；如果既有可能说真话也有可能说谎，输出 “Not defined”。

第一个样例中只有一个人，他自白为罪犯，且福尔摩斯知道有且仅有一个人说了实话。那么这个人一定在说实话。 第二个样例中有三名嫌疑人，每个人都否认自己的罪行。福尔摩斯知道只有两个人在说实话。任何一个都可能是罪犯，因此我们无法判断他们中谁一定说了实话，谁一定说了谎。 第三个样例中，第二和第四个嫌疑人分别为第一和第三个嫌疑人作证。但只有一个人在说实话，因此第一或第三人为罪犯。两者都可能是罪犯，所以第二和第四个人可能说了实话也可能说了谎，无法确定。而第一和第三个人则肯定说了谎，因为他们指认了第二和第四个人。 由 ChatGPT 5 翻译