Rezolvare PBinfo #2187

Ana şi Bogdan au inventat un nou joc, pe care l-au numit Expand. Jocul are N cartonaşe, pe fiecare cartonaş fiind scrisă o literă şi o secvenţă formată din două sau trei litere. O mutare constă în utilizarea unui cartonaş prin care o singură apariţie a literei scrisă pe cartonaş va fi înlocuită în cuvântul curent cu secvenţa corespunzătoare de pe cartonaş. Apoi cartonaşul este repus în joc, astfel că acelaşi cartonaş poate fi utilizat de oricâte ori. Iniţial Ana alege o literă şi un cuvânt. Bogdan trebuie să obţină cuvântul spus de Ana, plecând de la litera respectivă, efectuând un număr minim de mutări.

Cerința

Scrieţi un program care determină numărul minim de mutări necesare pentru a obţine din litera aleasă de Ana cuvântul dat.

Date de intrare

Fișierul de intrare expand.in conţine pe prima linie litera şi cuvântul alese de Ana, separate printr-un singur spaţiu. Pe a doua linie este scris un număr natural N, reprezentând numărul de cartonaşe din joc. Pe următoarele N linii sunt descrise cartonaşele. O linie care descrie un cartonaş conţine litera scrisă pe cartonaş, apoi secvenţa corespunzătoare separate printr-un singur spaţiu.

Date de ieșire

Fișierul de ieșire expand.out va conţine o singură linie pe care va fi scris numărul minim de mutări necesare pentru a obţine cuvântul ales de Ana din litera dată.

Restricții și precizări

• 1 ≤ N ≤ 15
• Toate literele sunt litere mici ale alfabetului englez.
• Lungimea cuvântului ales de Ana este cel mult 15.
• Pentru datele de test există întotdeauna soluţie.

Exemplu:

expand.in

a anatol
8
x yy
a aa
a ana
a ato
a tol
n na
n nat
t tol

expand.out

3

Explicație

Din litera a trebuie să obţinem cuvântul anatol
Alegem mai întâi cartonaşul a ana
Astfel am transformat litera a în cuvântul ana
Alegem cartonaşul n na şi înlocuim ultimul n cu na, obţinând anaa
Alegem cartonaşul a tol şi înlocuim ultimul a cu tol obţinând anatol
Numărul de mutări efectuate este 3.