CLASA a X-a
Problema 1:


Impratul VreaS^tieTot dore_te s afle despre toci supu_ii lui, dac sunt oameni cinstici (care nu mint niciodat) sau sunt mincino_i. El _tie c majoritatea supu_ilor si sunt oameni cinstici, dar pentru a avea o evidenc sigur, _i ntreab supu_ii care este prerea lor despre ceilalci. Un supus cinstit va spune ntotdeauna adevrul: ntrebat care e prerea lui despre un mincinos, va rspunde nendoielnic c acesta minte, iar despre un om cinstit, c nu minte niciodat. n schimb, un mincinos va minci ntotdeauna: va spune despre un om cinstit c minte, iar despre unul asemeni lui, c este cinstit.
Cum mprcia este foarte mare, este posibil ca un supus s nu _i cunoasc toci semenii.
Ajutaci mpratul s obcin evidenca dorit. Eliminaci toate acele rspunsuri care nu sunt necesare determinrii celor dou categorii de supu_i.

Date de intrare:
  Pe prima linie a fi_ierului de intrare INPUT.TXT este scris un numr ntrg n, reprezentnd numrul de supu_i (2(n(255);
  Pe urmtoarele linii sunt scrise triplete de forma: x c y unde:
  x _i y sunt numere ntregi, (2(n(255); x reprezent numrul de ordine al supusului care este interogat referitor la persoana al crui numr de ordine este y;
  c este un caracter _i poate fi:  c , semnificnd faptul c x spune despre y c acesta este cinstit, respectiv  m  dac x spune despre y c acesta este mincinos; cele trei valori sunt desprcite prin cte un spaciu.

Date de ie_ire:
  Pe prima linie a fi_ierului OUTPUT.TXT se va scrie un numr ntreg m, care reprezint numrul minim de triplete necesare pentru aflarea felului supu_ilor;
  Pe urmtoarele m linii se vor scrie tripletele seleccionate ca fiind suficiente pentru mprat, n aceea_i form ca n fi_ierul de intrare; 
  Pe urmtoarele dou linii se vor scrie cele dou categorii de supu_i, n_irnd numerele de ordine ale persoanelor, desprcite prin cte un spaciu. Pe prima linie se vor scrie numerele de ordine ale persoanelor cinstite, pe linia urmtoare se vor scrie mincino_ii.
Observacii:
1) n cazul n care din datele cuprinse n fi_ierul de intrare se pot selecta mai multe seturi de triplete avnd acela_i numr de elemente, se va afi_a doar unul.
2) n cazul n care datele de intrare nu sunt suficiente, n fi_ierul de ie_ire se va scrie:  Date insuficiente .
3) Datele de intrare nu necesit validare.
Exemple:
INPUT1.TXTOUTPUT1.TXTINPUT2.TXTOUTPUT2.TXT5
1 c 2
2 c 3
1 m 4
2 m 4
5 c 4
3 c 24
1 c 2
2 c 3
3 c 4
1 m 4
1 2 3
4 57
1 c 2
2 c 3
3 c 4
2 m 5
2 m 6
1 c 4
5 c 6
3 c 2Date insuficiente
Timp maxim de executare/test: o secund.
Punctaj maxim: 30 puncte
Olimpiada Nacional de Informatic
Oradea 27 martie   4 aprilie
