Directorul
scolii doreste sa afle despre fiecare elev din scoala daca este cinstit (nu
minte niciodata) sau este mincinos. El stie cu siguranta ca cel putin jumatate
dintre elevi sunt cinstiti, dar ar dori sa afle cu exactitate caracterul fiecarui
elev.
În
acest scop, numeroteaza elevii de la 1
la n, aseaza elevii in
rand, intr-o ordine oarecare, apoi solicita
fiecare elev sa isi exprime parerea despre colegii situati in rand dupa el.
Un elev cinstit va spune întotdeauna adevarul: întrebat care e parerea
lui despre un mincinos, va raspunde neîndoielnic ca acesta minte, iar
despre un elev cinstit, ca nu minte niciodata. În schimb, un mincinos
va minti întotdeauna: va spune despre un elev cinstit ca minte, iar despre
unul asemenea lui, ca este cinstit.
Cum scoala este foarte mare, este posibil ca un elev sa nu îsi cunoasca
toti colegii, dar din afirmatiile elevilor se poate deduce in mod unic ordinea
in care acestia au fost asezati in rand.
Cerinta
Scrieti un program care
sa determine pentru fiecare elev daca minte sau este daca cinstit.
Date de
intrare
Fisierul de intrare honest.in
contine pe prima linie
doua numere naturale separate printr-un spatiu n
m, reprezentând numarul de elevi, respectiv numarul de pareri
exprimate. Pe fiecare dintre urmatoarele m
linii sunt scrise triplete de forma: x
c y unde x si y
sunt numere întregi, (1 <=
x, y <= n); x
reprezinta numarul de ordine al elevului care este interogat referitor la elevul
cu numarul de ordine y;
c este un caracter si
poate fi: 'c', semnificând
faptul ca x spune despre
y ca acesta este cinstit,
respectiv 'm' daca x
spune despre y ca acesta
este mincinos; cele trei valori sunt despartite prin câte un spatiu.
Date de
iesire
Fisierul de iesire honest.out
va contine n
linii, cate una pentru fiecare supus. Pe linia i
se va scrie cifra 1 daca
elevul i este cinstit,
respectiv cifra 0 daca
elevul i este mincinos.
Restrictii si precizari
1 < n <= 1000
0
< m <= 200 000
Exemplu
honest.in
honest.out
5 9
1 c 2
2 c 3
1 m 4
2 m 4
5 c 4
3 m 4
1 m 5
2 m 5
5 m 3