Gigantikus reakciók

Brit tudósok egy titkos kutatáson dolgoznak. Olyan új, igen reaktív atomokat találtak, melyek bárhol, bármikor átalakulhatnak. Most épp egy olyan szimulációt végeznek, mellyel szeretnének pontosabb képet alkotni az atomokról. A különböző állapotú atomok egy sorozatát egy sztringgel reprezentáljuk. Az atomokat '+' karakterek választják el egymástól, egy atom egy állapotát pedig egy tetszőleges, nem üres, '+' karaktert nem tartalmazó sztring jelképezi. Az azonos sztringek mindig azonos állapotot jelentenek. Azt már megfigyelték, hogy az atomok sorrendje sosem rendeződik át. A tudósok tettek már megállapításokat arra vonatkozóan is, hogy az atomok milyen átalakulásokon eshetnek át. Tudni lehet, hogy minden állapotból egy lépésben legfeljebb egy másik állapotba kerülhetnek. Egy sorozat bármely eleme bármelyik pillanatban átalakulhat, és azt sosem lehet megjósolni, hogy egyszerre hány atom lép reakcióba.

A bemenet specifikációja

A bemenet első sora egy S₁[+S₂]… formátumú sztringet tartalmaz, mely a sorozat aktuális állapotát írja le. A következő sorban egy N pozitív egész szám szerepel, mely a lehetséges állapotváltások számát adja meg (1 ≤ N ≤ 10). Ezt a sort pontosan N darab X Y formátumú sor követi, ahol X egy atom olyan állapota, mely bármelyik pillanatban Y állapotra válthat. Biztos lehetsz benne, hogy az átmenetekben nem alakulhat ki ciklikusság, és minden X érték csak egyszer fordul elő a bemeneten.

A kimenet specifikációja

A program írja a standard kimenet első sorába azt, hogy hány különböző állapot alakulhat ki akkor, ha reakcióba lépnek a részecskék! Ezután minden sorba pontosan egy lehetséges állapot kerüljön, az őket reprezentáló sztringek lexikografikus sorrendjében! A bemenetként kapott állapot ne szerepeljen a kimenet sorai között!

Példa bemenet

1. a1+a2+b2
2. 3
3. a1 a0
4. a2 a1
5. b2 b0

letöltés szöveges állományként

A példa bemenethez tartozó kimenet

1. 12
2. a0+a0+b0
3. a0+a0+b2
4. a0+a1+b0
5. a0+a1+b2
6. a0+a2+b0
7. a0+a2+b2
8. a1+a0+b0
9. a1+a0+b2
10. a1+a1+b0
11. a1+a1+b2
12. a1+a2+b0

letöltés szöveges állományként