As Sherlock Holmes was investigating a crime, he identified n suspects. He knows for sure that exactly one of them committed the crime. To find out which one did it, the detective lines up the suspects and numbered them from 1 to n. After that, he asked each one: "Which one committed the crime?". Suspect number i answered either "The crime was committed by suspect number ai", or "Suspect number aididn't commit the crime". Also, the suspect could say so about himself (ai = i).
Sherlock Holmes understood for sure that exactly m answers were the truth and all other answers were a lie. Now help him understand this: which suspect lied and which one told the truth?
InputThe first line contains two integers n and m (1 ≤ n ≤ 105, 0 ≤ m ≤ n) — the total number of suspects and the number of suspects who told the truth. Next n lines contain the suspects' answers. The i-th line contains either "+ai" (without the quotes), if the suspect number isays that the crime was committed by suspect number ai, or "-ai" (without the quotes), if the suspect number i says that the suspect number ai didn't commit the crime (ai is an integer, 1 ≤ ai ≤ n).
It is guaranteed that at least one suspect exists, such that if he committed the crime, then exactly m people told the truth.
OutputPrint n lines. Line number i should contain "Truth" if suspect number i has told the truth for sure. Print "Lie" if the suspect number ilied for sure and print "Not defined" if he could lie and could tell the truth, too, depending on who committed the crime.
Examples input 1 1 +1 output Truth input 3 2 -1 -2 -3 output Not defined Not defined Not defined input 4 1 +2 -3 +4 -1 output Lie Not defined Lie Not defined NoteThe first sample has the single person and he confesses to the crime, and Sherlock Holmes knows that one person is telling the truth. That means that this person is telling the truth.
In the second sample there are three suspects and each one denies his guilt. Sherlock Holmes knows that only two of them are telling the truth. Any one of them can be the criminal, so we don't know for any of them, whether this person is telling the truth or not.
In the third sample the second and the fourth suspect defend the first and the third one. But only one is telling the truth, thus, the first or the third one is the criminal. Both of them can be criminals, so the second and the fourth one can either be lying or telling the truth. The first and the third one are lying for sure as they are blaming the second and the fourth one.
题意：n个嫌疑人 其中有一个是罪犯 然后m句真话
接下来n行代表n个人说的话
+x 代表 i 说 x是罪犯 -x 代表 i 说 x不是罪犯
问这些人说的话的真假情况
题解：我们先统计出每个人被说成是罪犯的次数和不是罪犯的次数
定义a[i]为说i是罪犯的个数 b[i]为说i不是罪犯的个数
sum1代表+x的次数 sum2代表-x的次数
然后for i 对于每个i 我们假定i是罪犯 那么真话就是 a[i]+sum2-b[i]
然后判断下是否等于m 如果相等 那么我们就把 i 加入到答案
最后判断下有几个可行答案 如果只有一个 那么每个人说的话是不是粗鄙之语一下就能判断出来
如果有多个答案 那只要指控 x 是罪犯 x能在ans中找到的 就是不确定的 因为别的也有可能是罪犯 指控 x 但在ans中找不到的就是粗鄙之语
说 x 不是罪犯但是x能在ans中找到的 不确定 因为x有可能是罪犯 说 x 不是罪犯 x在ans中找不到的就是天籁之音
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #include<vector> using namespace std; int a[100005],b[100005],d[100005],sum1,sum2,ans[100005],cnt; int main(){ int i,j,n,m; scanf("%d%d",&n,&m); getchar(); for(i=1;i<=n;i++){ char s=getchar(); scanf("%d",&d[i]); if(s=='-'){ d[i]=-d[i]; b[-d[i]]++; sum2++; } else{ a[d[i]]++; sum1++; } getchar(); } int flag=0; for(i=1;i<=n;i++){ int d=a[i]+sum2-b[i]; if(d==m){ ans[++cnt]=i; } } if(cnt==1){ for(i=1;i<=n;i++){ if(d[i]<0){ if(d[i]!=-ans[1])printf("Truth\n"); else printf("Lie\n"); } else{ if(d[i]==ans[1])printf("Truth\n"); else printf("Lie\n"); } } } else{ for(i=1;i<=n;i++){ int t=d[i]; int dt=lower_bound(ans+1,ans+1+cnt,abs(d[i]))-ans; if(d[i]<0){ if(ans[dt]!=-d[i])printf("Truth\n"); else printf("Not defined\n"); } else{ if(ans[dt]==d[i])printf("Not defined\n"); else printf("Lie\n"); } } } return 0; }
