minerale

Minerale

== include(page="template/taskheader" task_id="minerale") ==

Poveste şi cerinţă...

p>. ~La început a fost haosul şi din haos s-a desprins Pământul.~
 
p<>. 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.
 
h2. Cerinţă
 
p<>. 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ă.

h2. Date de intrare

Fişierul de intrare $minerale.in$ ...

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.

h2. Date de ieşire