問題文

英小文字のみからなる $2$ つの文字列 $S,T$ が与えられます。

高橋君は文字列 $S$ から始めて、 次の $K$ 種類の操作のうち $1$ つを選んで行う事を 好きなだけ繰り返す事ができます。
$i$ 番目の操作は次の形で与えられます。

コストを $1$ 支払う。 その後、文字列中に文字 $C_i$ が含まれるとき、そのうちの $1$ つを選び、文字列 $A_i$ に置き換える。 含まれないならば何も行わない。

文字列を $T$ と一致させるために必要な最小コストを求めてください。 ただし、$T$ と一致させることが不可能な場合は $\-1$ を出力してください。

制約

• $1\\leq |S|\\leq |T|\\leq 50$
• $1\\leq K\\leq 50$
• $C_i$ は a, b,$\\ldots$, z のいずれか
• $1\\leq |A_i|\\leq 50$
• $S,T,A_i$ は英小文字のみからなる文字列
• $C_i$ を長さ $1$ の文字列としてみた時、$C_i\\neq A_i$
• $(C_i,A_i)$ はすべて異なる。

入力

入力は以下の形式で標準入力から与えられる。

$S$ $T$ $K$ $C_1$ $A_1$ $C_2$ $A_2$ $\\vdots$ $C_K$ $A_K$

出力

$S$ を $T$ と一致させるために必要な最小コストを出力せよ。 ただし、$T$ と一致させることが不可能な場合は $\-1$ を出力せよ。

入力例 1

ab
cbca
3
a b
b ca
a efg

出力例 1

4

高橋君は $S=$ab から始めて、次のように $4$ 回操作を行う事で、 $T=$cbca を作ることができます。

• ab の $1$ 文字目 a を選んで b に置き換える ( $1$ 番目の操作) 。文字列は bb となる。
• bb の $2$ 文字目 b を選んで ca に置き換える ( $2$ 番目の操作) 。文字列は bca となる。
• bca の $1$ 文字目 b を選んで ca に置き換える ( $2$ 番目の操作) 。文字列は caca となる。
• caca の $2$ 文字目 a を選んで b に置き換える ( $1$ 番目の操作) 。文字列は cbca となる。

各操作においてコストが $1$ かかるため、必要なコストは $4$ となり、このときが最小です。

入力例 2

a
aaaaa
2
a aa
a aaa

出力例 2

2

a$\\to$aaa$\\to$aaaaa とした時、必要なコストは $2$ となり、 このときが最小です。

入力例 3

a
z
1
a abc

出力例 3

-1

どのように操作を行っても、$S=$a から $T=$z を作る事は出来ません。