Problem Statement

You are given two strings $S$ and $T$ consisting of lowercase English letters.

Takahashi starts with the string $S$. He can perform $K$ kinds of operations any number of times in any order. The $i$-th operation is the following:

Pay a cost of $1$. Then, if the current string contains the character $C_i$, choose one of its occurrences and replace it with the string $A_i$. Otherwise, do nothing.

Find the minimum total cost needed to make the string equal $T$. If it is impossible to do so, print $-1$.

Constraints

• $1\leq |S|\leq |T|\leq 50$
• $1\leq K\leq 50$
• $C_i$ is a, b,$\ldots$, or z.
• $1\leq |A_i|\leq 50$
• $S$, $T$, and $A_i$ are strings consisting of lowercase English letters.
• $C_i\neq A_i$, regarding $C_i$ as a string of length $1$.
• All pairs $(C_i,A_i)$ are distinct.

Input

Input is given from Standard Input in the following format:

S
T
K
C_1 A_1
C_2 A_2
\vdots
C_K A_K

Output

Print the minimum total cost needed to make the string equal $T$. If it is impossible to do so, print $-1$.