配点 : $600$ 点

問題文

英小文字のみからなる $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$ を出力せよ。

ab
cbca
3
a b
b ca
a efg

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$ となり、このときが最小です。

a
aaaaa
2
a aa
a aaa

2

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

a
z
1
a abc

-1

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