替换

题目描述

给定两个由小写英文字母组成的字符串 $S$ 和 $T$。

Takahashi 从字符串 $S$ 开始。他可以按任意顺序、任意次数执行 $K$ 种操作。

第 $i$ 种操作如下:

支付 $1$ 的费用。 然后,如果当前字符串包含字符 $C_i$,则选择其中一个出现位置,将其替换为字符串 $A_i$。 否则,不做任何事。

求使字符串等于 $T$ 所需的最小总费用。 如果不可能,则输出 $-1$。

输入格式

输入按以下格式从标准输入给出：

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

输出格式

输出使字符串等于 $T$ 所需的最小总费用。 如果不可能,则输出 $-1$。

样例

ab
cbca
3
a b
b ca
a efg

4

从 $S=$ab 开始,Takahashi 可以用四次操作得到 $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。

数据范围

• $1 \le |S| \le |T| \le 50$
• $1 \le K \le 50$
• $C_i$ 为 a、b、$\ldots$、z 中的某个字符
• $1 \le |A_i| \le 50$
• $S$、$T$ 和 $A_i$ 是由小写英文字母组成的字符串
• $C_i \neq A_i$(将 $C_i$ 视为长度为 $1$ 的字符串)
• 所有 $(C_i,A_i)$ 对两两不同