Ucenicul vrajitor a luat eprubeta magica si toarna in ea doze din cele 32 solutii vrajite ale maestrului. Solutiile se aseaza in straturi consecutive si uneori doza turnata reactioneaza cu solutiile deja existente in eprubeta, astfel ca ucenicul se intreaba dupa mai multe operatii ce solutii  mai contine eprubeta.
 Se cunosc urmatoarele:
- exista m combinatii de solutii care aflate in straturi succesive (fara alte substante intre ele) dau nastere unei alte solutii
- nu conteaza ordinea in care sunt asezate solutiile care reactioneaza, dar conteaza cantitatea, mai exact reactia are loc doar daca din fiecare solutie exista o singura doza, iar ca rezultat se obtine tot o doza din noua solutie
- doua doze consecutive din aceeasi solutie reactioneaza, obtinandu-se o doza din aceeasi solutie.
- daca sunt posibile mai multe reactii, se produce cea care implica cat mai putine solutii.
O solutie este identificata de una dintre cele 26 litere mari ale alfabetului englez sau de una dintre cifrele 1, 2, 3, 4, 5, 6.
O reactie este specificata sub forma s₁s₂...s_k=s, unde s₁, s₂, ..., s_k reprezinta solutiile care se combina, iar s este solutia obtinuta in urma reactiei.

Cerinta

Pe prima linie a fisierului de intrare chimie.in sunt scrise numerele naturale m si n: numarul de reactii chimice posibile si numarul de doze turnate in eprubeta. Pe urmatoarele m linii sunt date reactiile chimice, cate o reactie pe o linie. Pe urmatoarele n linii sunt date solutiile in ordinea in care sunt turnate in eprubeta, cate o solutie pe o linie.

Prima linie a fisierului chimie.out va contine  numarul solutiilor existente in eprubeta la sfarsit. Pe urmatoarele linii sunt scrise solutiile, cate una pe linie, in ordinea straturilor, incepand cu stratul cel mai de jos.

• 2 <= n <= 100000
• 1 <= m <= 70000
• In specificarea reactiilor chimice nu apar spatii.

Exemplu

chimie.in	chimie.out	Explicatie
4 8 ABC=D BD=C CDA=B AD=C E A B A D C B D	3 E D C	1. E 2. EA 3. EAB 4. EABA 5. EABAD=>EABC=>ED 6. EDC 7. EDCB 8. EDCBD=>EDCC=>EDC

Timp maxim de executie/test: 0.3 secunde