Mica Alchimie

Cerință

Conform alchimiștilor medievali, universul este compus din patru elemente de bază: apa, aer, pamant și foc. Plecând de la aceste elemente, se pot realiza reacții alchimice pentru a obține noi substanțe.

Vi se dă o listă de $R$ reacții, fiecare de forma:

$\text{elem}_1 + \text{elem}_2 + \dots + \text{elem}_C \Rightarrow \text{rezultat}$

care descrie că, dacă aveți simultan la dispoziție elementele $\text{elem}_1, \text{elem}_2, \dots, \text{elem}_C$, puteți obține elementul rezultat. Elementele nu se consumă la aplicarea unei reacții — odată obținut, un element rămâne disponibil pentru reacțiile ulterioare.

Obiectivul vostru este să determinați o secvență de reacții care duce, pornind de la cele patru elemente de bază, la obținerea elementului piatra-filozofala.

Date de intrare

Prima linie conține numărul întreg $R$. Urmează $R$ linii, fiecare descriind o reacție în formatul de mai sus. Niciun element nu apare de două ori în partea stângă a aceleiași reacții.

Date de ieșire

Pe prima linie, afișați numărul $K$ de reacții din secvența voastră. Urmează $K$ linii, fiecare conținând o reacție (dintre cele $R$ reacții disponibile), în ordinea aplicării lor, astfel încât la momentul aplicării fiecărei reacții toate elementele din stânga să fie deja disponibile, iar la final piatra-filozofala să fie disponibilă.

Orice secvență validă cu cel mult $R$ reacții este acceptată.

Restricții și precizări

• $1 \leq R \leq 20 \ 000$
• Numărul total de elemente distincte este cel mult $N \leq 10 \ 000$ (inclusiv cele patru elemente de bază)
• Fiecare reacție are cel mult $C \leq 100$ elemente în partea stângă
• Numele elementelor sunt formate din litere mici ale alfabetului latin, cifre și cratimă (-), cu lungime de cel mult $20$ de caractere
• Se garantează că piatra-filozofala poate fi obținută pornind de la cele patru elemente de bază

Exemplu

stdin

8
apa + foc => aburi
aer + pamant => noroi
aburi + noroi => ceata
foc + pamant => carbune
ceata + carbune => piatra-filozofala
apa + aer => vant
foc + vant => lumina
pamant + aer + foc => taran

stdout

5
apa + foc => aburi
aer + pamant => noroi
aburi + noroi => ceata
foc + pamant => carbune
ceata + carbune => piatra-filozofala

Explicație

Cele trei reacții de la final (vant, lumina, taran) nu sunt necesare pentru a obține piatra-filozofala și nu apar în output. Ordinea reacțiilor din output poate varia; orice secvență validă este acceptată.