当前没有测试数据。

G - 替换

分值：$600$ 分

问题描述

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

高桥从字符串 $S$ 开始。他可以按照任意顺序多次执行 $K$ 种操作。
第 $i$ 次操作如下：

支付花费为 $1$ 的代价。 然后，如果当前字符串中包含字符 $C_i$，选择其中一个出现位置并将其替换为字符串 $A_i$。 否则，什么也不做。

找出使得字符串等于 $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$

输出

输出使得字符串等于 $T$ 的最小总花费。 如果无法实现，则输出 $-1$。

ab
cbca
3
a b
b ca
a efg

4

从 $S=$ab 开始，高桥可以按照以下四次操作使得 $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

无论进行怎样的操作，无法使 $T=$z 从 $S=$a 变为。