Problem Description
After showing you his awesome, eye catching dance, Guan has suddenly ended up in another room in the dance arena.
In this room are p people, of two kinds, Liars and Truth Tellers. Liars always lie and Truth Tellers always tell the truth.
Each of the people in this room will make multiple statements about the other people in this room and there will be n statements in total.
Each person will either state that another person is telling the truth or lying (Each person knows every other person's identities and A liar will state that another person who tells the truth is lying) or he(/she) will state that the other person is either of the same or of a different type.
After hearing so many statements, Guan is confused and has hurt himself in his confusion :-(
Guan would like you to help him find out which people are definitely liars or truth tellers so that he can know who to trust.
An Illustration
XKCD 246
Another Illustration
Input
The first line of the input will be the number of people, p followed by the number of statements, n
The rest of the lines of input will consist of a single integer, i indicating the id of the person who said the statement, followed by another integer j indicating the id of the person he(/she) is referring to and finally, a string saying either TRUTH, LIAR, SAME or DIFFERENT to indicate whether he(/she) says the other person is telling the truth, lies or is of the same type as herself or of a different type to herself.
It is guaranteed that there will be no contradictory or repeated statements and people may comment about themselves
Note: A person can comment on him(/her)self
Output
A single of characters which indicate 'T' if a person is definitely a truth teller, 'F' if he(/she) is definitely a liar and '?' otherwise
Subtasks
Subtask 1 (11%) p,n<=20
Subtask 2 (18%) p,n<=1000
Subtask 3 (9%) p,n<=1000000, there will be no SAME or DIFFERENT statements
Subtask 4 (17%) p,n<=1000000, there will be no TRUTH or LIAR statements
Subtask 5 (45%) p,n<=1000000, no further restrictions
Subtask 6 (0%) will be the sample testcases
Sample Testcase 1
Input
5 5
1 2 TRUTH
1 3 LIAR
1 4 DIFFERENT
4 1 SAME
1 5 TRUTH
Output
TTFFT
Explanation
1 always tells the truth, so he will say 2 is telling the truth, 3 is lying, 4 is different and 5 is telling the truth. 4 is lying, so he will say 1 is the same. No other combination of 5 people results in the same pairs of statements
Sample Testcase 2
Input
3 2
1 2 SAME
2 1 SAME
Output
TT?
Explanation
Either TTF or TTT satisfy the above statements, so, we do not know whether the 3rd person is telling the truth or lying