expand

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ţă

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

• $1 \leq N \leq 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.

Exemplul 1

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$.