题目描述

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

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

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

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

输入格式

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

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

输出格式

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

题目大意

先给定两个字符串 $S$ 和 $T$，并给定 $n$ 种操作，第 $i$ 个操作可以把 $S$ 中的字符 $c_i$ 替换成字符串 $s_i$。你的目标就是使用若干次操作，使得 $S$ 变成 $T$.

所有涉及字母均为小写字母。

数据范围

• $1\leqslant|S|,|T|\leqslant 50$
• $1\leqslant n\leqslant50$
• $1\leqslant|s_i|\leqslant50$

ab
cbca
3
a b
b ca
a efg

4

a
aaaaa
2
a aa
a aaa

2

a
z
1
a abc

-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)$ はすべて異なる。

Sample Explanation 1

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

Sample Explanation 2

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

Sample Explanation 3

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