G - Replace Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 600 点

問題文

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

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

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

文字列を T と一致させるために必要な最小コストを求めてください。 ただし、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

出力

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

入力例 1

ab
cbca
3
a b
b ca
a efg

出力例 1

4

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

入力例 2

a
aaaaa
2
a aa
a aaa

出力例 2

2

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

入力例 3

a
z
1
a abc

出力例 3

-1

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

Score : 600 points

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.