← 返回题目列表

AtCoder · abc261_g

G. 更换

中文机器翻译题面 查看原题

分数: 600 点

问题陈述

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

Takahashi 以字符串开头 S。他可以表演 K 种操作可以任意顺序任意次数。
的 i第操作如下:

支付费用 1。 那么,如果当前字符串包含 字符 C_i,选择其出现之一并将其替换为 字符串 A_i。 否则,什么也不做。

找出使字符串相等所需的最小总成本 T。 如果无法做到这一点,请打印 -1.

约束

  • 1\leq |S|\leq |T|\leq 50
  • 1\leq K\leq 50
  • C_i is a, b,\ldots,或 z.
  • 1\leq |A_i|\leq 50
  • S, T,和 A_i 是由小写英文字母组成的字符串。
  • C_i\neq A_i,关于 C_i 作为长度的字符串 1.
  • 所有对 (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 四次操作如下:

  • 更换 1-st 字符 a in ab 与 b (操作 1-st 种)。字符串现在是 bb.
  • 更换 2-nd 字符 b in bb 与 ca (操作 2-nd 种)。字符串现在是 bca.
  • 更换 1-st 字符 b in bca 与 ca (操作 2-nd 种)。字符串现在是 caca.
  • 更换 2-nd 字符 a in caca 与 b (操作 1-st 种)。字符串现在是 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.