Clasa a X-a
Ziua 1
Problema 2

Mincinosi

Īmparatul VreaSaStieTot doreste sa afle despre toti supusii lui, daca sunt oameni cinstiti (care nu mint niciodata) sau sunt mincinosi. El stie ca majoritatea supusilor sai sunt oameni cinstiti, dar pentru a avea o evidenta sigura, īsi īntreaba supusii care este parerea lor despre ceilalti. Un supus cinstit va spune īntotdeauna adevarul: īntrebat care e parerea lui despre un mincinos, va raspunde neīndoielnic ca acesta minte, iar despre un om cinstit, ca nu minte niciodata. Īn schimb, un mincinos va minti īntotdeauna: va spune despre un om cinstit ca minte, iar despre unul asemeni lui, ca este cinstit.
Cum īmparatia este foarte mare, este posibil ca un supus sa nu īsi cunoasca toti semenii.
Ajutati īmparatul sa obtina evidenta dorita. Eliminati toate acele raspunsuri care nu sunt necesare determinarii celor doua categorii de supusi.

Date de intrare:
- Pe prima linie a fisierului de intrare INPUT.TXT este scris un numar īntreg n, reprezentānd numarul de supusi (2<=n<=4000);
- Pe urmatoarele linii sunt scrise triplete de forma: x c y unde:
- x si y sunt numere īntregi, (2<=x,y<=n); x reprezenta numarul de ordine al supusului care este interogat referitor la persoana al carui numar de ordine este 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:
- Pe prima linie a fisierului OUTPUT.TXT se va scrie un numar īntreg m, care reprezinta numarul minim de triplete necesare pentru aflarea felului supusilor;
- Pe urmatoarele m linii se vor scrie tripletele selectionate ca fiind suficiente pentru Īmparat, īn aceeasi forma ca īn fisierul de intrare;
- Pe urmatoarele linii se vor scrie numerele de ordine ale persoanelor cinstite, despartite prin cāte un spatiu. Aceste numere se vor scrie īn fisier (40 pe o linie, exceptānd ultima), īn ordine crescatoare.
- Īn fisier va urma o linie vida, apoi se vor scrie, īn mod similar, numerele de ordine ale supusilor mincinosi.
Observatii:
1) Īn cazul īn care din datele cuprinse īn fisierul de intrare se pot selecta mai multe seturi de triplete avānd acelasi numar de elemente, se va afisa doar unul.
2) Īn cazul īn care datele de intrare nu sunt suficiente, īn fisierul de iesire se va scrie: 'Date insuficiente'.
3) Datele de intrare nu necesita validare.
Exemple:
INPUT1.TXT
5
1 c 2
2 c 3
1 m 4
2 m 4
5 c 4
3 c 2

OUTPUT1.TXT
4
1 c 2
2 c 3
5 c 4
1 m 4
1 2 3
4 5

INPUT2.TXT
7
1 c 2
2 c 3
3 c 4
2 m 5
2 m 6
1 c 4
5 c 6
3 c 2

OUTPUT2.TXT
Date insuficiente

Timp maxim de executare/test: o secunda.
Punctaj maxim: 30 puncte