The school principal wants to find out about every pupil if he/she is honest (never lies) or is a liar. He knows for sure that at least half of the pupils are honest but he would like to know the exact character of every pupil.
For this purpose he numbers students from 1 to n, lines up the pupils in random order and then asks every pupil to express his/her opinion about the colleagues that are in line after them. An honest pupil will always tell the truth: when asked what he thinks about a liar he will undoubtedly answer that he/she is a liar and about an honest student that he/she never lies. On the other hand a liar will always lie: a liar will always say about an honest pupil that he/she is a liar and about one like himself/herself that he/she is honest.
Seeing as the school is very big it is possible that a student not know all his colleagues but using their statements one can uniquely realize in what order they were lined up.
Task
Write a program that would determine for every student whether he/she is honest.
Input data
Input file honest.in contains on the first line two positive integers n m separated by a space, representing the number of students and, respectively, the number of expressed opinions. Each of the following m lines contains triplets in the form: x c y where x and y are integers, (1 <= x, y <= n); x represents the number of the student that is being questioned regarding student number y; c is a character and can be: 'c', representing that x is saying about y that he/she is honest, respectively 'm' if x is saying about y that he/she is a liar; the three values are separated by a space.
Output data
Output file honest.out shall contain n lines, one for each subject. Line i will contain a 1 if student i is honest, respectively a 0 if student i is a liar.
Constraints
| honest.in | honest.out |
|
5 8 |
1 |
Time limit: 0.6 seconds/test
prof. Emanuela
Cerchez
Computer Science
High School "Grigore Moisil"Iasi
Contact:emanuela.cerchez@gmail.com