AT_abc261_g [ABC261G] Replace

[problemUrl]: https://atcoder.jp/contests/abc261/tasks/abc261_g 英小文字のみからなる $ 2 $ つの文字列 $ S,T $ が与えられます。 高橋君は文字列 $ S $ から始めて、 次の $ K $ 種類の操作のうち $ 1 $ つを選んで行う事を 好きなだけ繰り返す事ができます。 $ i $ 番目の操作は次の形で与えられます。 > コストを $ 1 $ 支払う。 その後、文字列中に**文字** $ C_i $ が含まれるとき、そのうちの $ 1 $ つを選び、**文字列** $ A_i $ に置き換える。 含まれないならば何も行わない。 文字列を $ T $ と一致させるために必要な最小コストを求めてください。 ただし、$ T $ と一致させることが不可能な場合は $ -1 $ を出力してください。

入力は以下の形式で標準入力から与えられる。 > $ S $ $ T $ $ K $ $ C_1 $ $ A_1 $ $ C_2 $ $ A_2 $ $ \vdots $ $ C_K $ $ A_K $

$ S $ を $ 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) $ はすべて異なる。 ### Sample Explanation 1 高橋君は $ 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 $ となり、このときが最小です。 ### Sample Explanation 2 `a`$ \to $`aaa`$ \to $`aaaaa` とした時、必要なコストは $ 2 $ となり、 このときが最小です。 ### Sample Explanation 3 どのように操作を行っても、$ S= $`a` から $ T= $`z` を作る事は出来ません。