102616: [AtCoder]ABC261 G - Replace

Problem Statement

You are given two strings $S$ and $T$ consisting of lowercase English letters.

Takahashi starts with the string $S$. He can perform $K$ kinds of operations any number of times in any order.
The $i$-th operation is the following:

Pay a cost of $1$. Then, if the current string contains the character $C_i$, choose one of its occurrences and replace it with the string $A_i$. Otherwise, do nothing.

Find the minimum total cost needed to make the string equal $T$. If it is impossible to do so, print $-1$.

Constraints

• $1\leq |S|\leq |T|\leq 50$
• $1\leq K\leq 50$
• $C_i$ is a, b,$\ldots$, or z.
• $1\leq |A_i|\leq 50$
• $S$, $T$, and $A_i$ are strings consisting of lowercase English letters.
• $C_i\neq A_i$, regarding $C_i$ as a string of length $1$.
• All pairs $(C_i,A_i)$ are distinct.

Input

Input is given from Standard Input in the following format:

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

Output

Print the minimum total cost needed to make the string equal $T$. If it is impossible to do so, print $-1$.

Sample Input 1

ab
cbca
3
a b
b ca
a efg

Sample Output 1

4

Starting with $S=$ab, Takahashi can make $T=$cbca in four operations as follows:

• Replace the $1$-st character a in ab with b (Operation of the $1$-st kind). The string is now bb.
• Replace the $2$-nd character b in bb with ca (Operation of the $2$-nd kind). The string is now bca.
• Replace the $1$-st character b in bca with ca (Operation of the $2$-nd kind). The string is now caca.
• Replace the $2$-nd character a in caca with b (Operation of the $1$-st kind). The string is now cbca.

Each operation incurs a cost of $1$, for a total of $4$, which is the minimum possible.

Sample Input 2

a
aaaaa
2
a aa
a aaa

Sample Output 2

2

Two operations a $\to$ aaa $\to$ aaaaa incur a cost of $2$, which is the minimum possible.

Sample Input 3

a
z
1
a abc

Sample Output 3

-1

No sequence of operations makes $T=$z from $S=$a.

问题描述

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

高桥启一开始有字符串$S$。他可以以任意顺序任意次数进行$K$种操作。

花费$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$。

样例输入1

ab
cbca
3
a b
b ca
a efg

样例输出1

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$，这是可能的最小值。

样例输入2

a
aaaaa
2
a aa
a aaa

样例输出2

2

两次操作a $\to$ aaa $\to$ aaaaa产生$2$的成本，这是可能的最小值。

样例输入3

a
z
1
a abc

样例输出3

-1

没有任何操作序列可以使$T=$z从$S=$a得到。