La început a fost haosul şi din haos s-a desprins Pământul.
La începutul începutului, pe Terra a existat o singură substanţă chimică S, numită substanţa primordială. Ulterior, din ea s-au format alte substanţe chimice, unele stabile (notate prin litere mici ale alfabetului englez), iar altele instabile (notate prin litere mari ale alfabetului englez). Substanţele stabile aveau proprietatea că nu se mai puteau transforma în alte substanţe, în timp ce o substanţă instabilă se putea transforma fie într-o substanţă stabilă, fie în două substanţe instabile. În urma reacţiilor chimice repetate s-au format mineralele, conglomerate de substanţe stabile. Unele dintre aceste minerale s-au format prin reacţii chimice care au pornit chiar din substanţa primordială S, în timp ce altele fie s-au format prin reacţii chimice care au pornit de la o altă substanţă instabilă existentă în acel moment pe Terra, dar nu din substanţa primordială S, fie, pur şi simplu, au fost aduse din spaţiul cosmic, deci nu s-au format în urma unor reacţii chimice pornite dintr-o substanţă instabilă de pe Terra.
Cerinţă
Cei mai mari cercetători contemporani ai haosului primordial, BitDAC şi rOCKTETU’, au reuşit să identifice toate reacţiile chimice care s-au produs de-a lungul timpului pe Terra. Scrieţi pentru ei un program care să stabilească dacă un mineral, cu formula dată sub forma unui şir de substanţe stabile, provine dintr-o substanţă instabilă de pe Terra, inclusiv din substanţa primordială S, sau este de origine extraterestră.
Date de intrare
Fişierul de intrare minerale.in conţine:
• pe prima linie două numere naturale nenule r şi m, reprezentând, în această ordine, numărul reacţiilor chimice şi numărul mineralelor ale căror origini vor fi analizate (substanţele stabile vor fi notate prin litere mici ale alfabetului englez, iar substanţele instabile prin litere mari ale alfabetului englez);
• pe fiecare dintre următoarele r rânduri se va găsi câte o reacţie chimică, respectiv fie un şir de caractere de forma A b, unde A este o substanţă instabilă şi b o substanţă stabilă, fie un şir de caractere de forma A BC, unde A, B şi C sunt 3 substanţe instabile.
• pe fiecare dintre următoarele m rânduri se va găsi formula unui mineral, respectiv un şir de caractere format din cel mult 100 de litere mici ale alfabetului englez.
Date de ieşire
Fişierul de ieşire minerale.out va conţine m linii, iar pe fiecare linie se va scrie unul dintre numerele 0, 1 sau 2, după cum mineralul cu numărul de ordine egal cu numărul de ordine al liniei este de origine extraterestră, provine din substanţa primordială S sau provine dintr-o altă substanţă instabilă alta decât substanţa primordială S.
Restricţii
• Substanţa primordială S este întotdeauna o substanţă instabilă..
• Orice mineral poate avea în compoziţia sa cel mult 100 de substanţe stabile.
• În cazul în care un mineral provine atît din substanţa primordială S, cât şi din alte substanţe instabile se va considera că el provine din substanţa primordială S.
• 1 ≤ r ≤ 400
• 1 ≤ m ≤ 100
Exemple
minerale.in
minerale.out
Explicaţii
8 3
S AB
S CA
A a
B BC
B BC
B AC
C AB
C b
aaaab
aaabb
abab
1
2
0
Mineralul aaaab se poate obţine din substanţa primordială S prin următoarele reacţii chimice: S→AB→aB→aAC→aaC→aaAB→aaaB→aaaAC→→aaaaC→aaaab.
Mineralul aaabb nu se poate obţine din substanţa primordială S, dar se poate obţine din susbstanţa instabilă B prin următoarele reacţii chimice: B→BC→ACC→aABC→aaBC→aaACC→aaaCC→ →aaabC→aaabb.
Mineralul abab nu se poate obţine din nici o substanţă instabilă.