Úloha: Generování slov

Jednoduchý zásobníkový automat má k dispozici množinu pravidel a z nich pomocí substitucí může generovat různá slova. Generované slovo je představováno vždy posloupností všech znaků uložených na zásobníku v pořadí ode dna.

Každé pravidlo je dvojice neprázdných řetězců, první řetězec se nazývá levá strana pravidla, druhý řetězec se nazývá pravá strana pravidla. V této úloze platí, že levá strana každého pravidla je kratší než jeho pravá strana.

V jedné substituci automat změní obsah zásobníku (vygeneruje nové slovo) tak, že zvolí libovolné pravidlo, jehož levá strana se shoduje s vrcholem zásobníku a nahradí znaky na vrcholu zásobníku pravou stranou pravidla. Vrcholem zásobníku rozumíme neprázdnou posloupnost sousedních znaků na zásobníku, jejíž poslední prvek je zároveň posledním znakem na zásobníku v pořadí ode dna.
Příklad (dno zásobníku je vlevo)
Zásobník před susbstitucí: ababacba
Pravidlo použité v substituci: acba cbaba
Zásobník po substituci: ababcbaba

Substituce: Nechť zásobník v pořadí ode dna obsahuje znaky a[1], ..., a[n] a nechť řetězec na levé straně pravidla se skládá ze znaků b[1], ..., b[m] a nechť řetězec na pravé straně pravidla se skládá ze znaků c[1], ..., c[k]. Před provedením susbstituce se znak a[n–m+1] musí shodovat se znakem b[1], znak a[n–m+2] se musí shodovat se znakem b[2], atd, až znak a[n] se musí shodovat se znakem b[m]. Po provedení substituce pomocí daného pravidla je na zásobníku posloupnost znaků (v pořadí ode dna): a[1], a[2], ..,. a[n–m], c[1], c[2], ..., c[k].

Pokud automat nemůže provést žádnou substituci, tj, levá strana žádného pravidla se neshoduje s vrcholem zásobníku, automat svou práci končí. Poznámka: Za vrchol zásobníku lze pokládat i celý zásobník.

Úlohou je zjistit, jestli automat s danou množinou pravidel může vygenerovat dané slovo, a pokud ano, jaký minimální počet substitucí je k tomu zapotřebí.

Slovo na vstupu má maximálně 100 znaků, skládá se pouze ze znaků 'a', .., 'z'. Každá strana každého pravidla se skládá rovněž pouze ze znaků 'a', .., 'z' a 'Z' a její délka nepřesáhne 100 znaků. Před začátkem práce automatu je na zásobníku jediný počáteční symbol 'Z' (velké z). Typicky proto musí levá strana alespoň jednoho pravidla obsahovat právě tento znak, jinak nelze z množiny pravidel generovat žádné slovo. Počáteční symbol nepočítáme do množiny generovaných slov. Při generování slova mohou některá pravidla zůstat nevyužita a jiná se mohou v jednotlivých substitucích v libovolném pořadí opakovat.

Vstup

Na vstupu je nejprve na jednom řádku slovo, o němž máme ověřit zda je automatem generovatelné. Dále následuje řádek s kladným celým číslem udávajícím počet pravidel a dále následují pravidla na každém řádku jedno, ve tvaru <levá_strana><mezera><pravá_strana>. Ve standardním značení pravidel se mezi levou a pravou stranou pravidla uvádí šipka, pro zjednodušení ji v této úloze na vstupu vypouštíme.

Výstup

Pokud slovo nelze pomocí daných pravidel generovat, vystoupí pouze řetězec [Impossible]. Jinak vystoupí jediné celé číslo udávající minimální počet substitucí, jimiž lze dané slovo generovat.

Příklad 1

Vstup:

bbbbbb
6
Z bb
b bb
Z ac
ac bbc
c bbc
c bb

Výstup:

4

Poznámka: Uvedený výstup je způsoben použitím pravidel Z –> ac, ac –> bbc, c –> bbc, c –> bb.
Možné jsou ještě dva další postupy generování slova bbbbbb, ale oba obsahují pět substitucí:
Z –> bb, b –> bb, b –> bb, b –> bb, b –> bb.
Z –> ac, ac –> bbc, c –> bb, b –> bb, b –> bb.

Příklad 2

Vstup:

abc
2
Z ab
a bc

Výstup:

[Impossible]

Příklad 3

Vstup:

aaaaaba
3
Z aaZ
Z ab
ab aba

Výstup:

4

Příklad 4

Vstup:

stststst
6
sst sstt
Z st
st sts
ts tsts
s st
t ts

Výstup:

5

Příklad 5

Vstup:

abcdeeedcba
10
Z pp
pp edc
edc edcb
edcb edcba
edcba abcdee
e ee
e ed
d dc
c cb
b ba

Výstup:

10