Sa consideram un grup format din N persoane, numerotate de la
1 la N. Aceste persoane pot fi impartite in doua categorii: persoane care spun
adevarul (categoria A) si persoane care mint (categoria F).
Toate persoanele din grup au fost chemate la un interviu. Aici fiecare persoana
a nominalizat cativa membri ai grupului, precizand ca acestia apartin uneia
dintre cele doua categorii.
Cerinta
Scrieti un program care, pe baza infomatiilor obtinute la interviu,
sa determine care persoane spun adevarul si care mint.
Date de intrare
Fisierul de intrare adevar.in
contine pe prima linie N, numarul de persoane din grup. Urmatoarele 2N linii contin afirmatiile persoanelor. Mai exact, afirmatiile persoanei i sunt plasate
pe liniile 2i si 2i+1 sub forma:
K A1 A2
... AK
L B1 B2 ... BL
Ceea ce inseamna ca persoana i a spus ca persoanele A1
A2 ... AK spun adevarul si ca persoanele
L B1 B2 ... BL mint.
Fiecare persoana face cel putin o afirmatie despre o alta persoana
si nici o persoana nu face afirmatii despre ea insasi. De asemenea, nici o persoana
nu va afirma ca o alta persoana spune adevarul, dar si minte in acelasi timp.
Daca o persoana spune adevarul, atunci toate afirmatiile persoanei respective trebuie sa fie adevarate. Daca o persoana minte, cel putin una dintre afirmatiile persoanei respective trebuie sa fie falsa.
Date de iesire
Fisierul de iesire adevar.out
contine N linii. Pe linia i se precizeaza daca persoana i spune adevarul sau
minte. Daca persoana i spune adevarul pe linia i se va afisa 0, altfel se va afisa 1.
Restrictii
2 <= N <= 20
Exista intotdeauna solutie pentru datele de test, nu neaparat
unica.
Exemple
adevar.in
adevar.out
3
1 3
0
0
1 1
1 1
0
0
1
0
adevar.in
adevar.out
4
1 2
1 3
1 4
0
0
1 4
0
1 3
0
0
1
0
prof. Emanuela Cerchez
Liceul de Informatica "Grigore Moisil" Iasi