{"raw_statement":[{"iden":"problem statement","content":"You are given two strings $S$ and $T$ consisting of lowercase English letters.\nTakahashi starts with the string $S$. He can perform $K$ kinds of operations any number of times in any order.  \nThe $i$\\-th operation is the following:\n\n> 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.\n\nFind the minimum total cost needed to make the string equal $T$. If it is impossible to do so, print $-1$."},{"iden":"constraints","content":"*   $1\\leq |S|\\leq |T|\\leq 50$\n*   $1\\leq K\\leq 50$\n*   $C_i$ is `a`, `b`,$\\ldots$, or `z`.\n*   $1\\leq |A_i|\\leq 50$\n*   $S$, $T$, and $A_i$ are strings consisting of lowercase English letters.\n*   $C_i\\neq A_i$, regarding $C_i$ as a string of length $1$.\n*   All pairs $(C_i,A_i)$ are distinct."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$S$\n$T$\n$K$\n$C_1$ $A_1$\n$C_2$ $A_2$\n$\\vdots$\n$C_K$ $A_K$"},{"iden":"sample input 1","content":"ab\ncbca\n3\na b\nb ca\na efg"},{"iden":"sample output 1","content":"4\n\nStarting with $S=$`ab`, Takahashi can make $T=$`cbca` in four operations as follows:\n\n*   Replace the $1$\\-st character `a` in `ab` with `b` (Operation of the $1$\\-st kind). The string is now `bb`.\n*   Replace the $2$\\-nd character `b` in `bb` with `ca` (Operation of the $2$\\-nd kind). The string is now `bca`.\n*   Replace the $1$\\-st character `b` in `bca` with `ca` (Operation of the $2$\\-nd kind). The string is now `caca`.\n*   Replace the $2$\\-nd character `a` in `caca` with `b` (Operation of the $1$\\-st kind). The string is now `cbca`.\n\nEach operation incurs a cost of $1$, for a total of $4$, which is the minimum possible."},{"iden":"sample input 2","content":"a\naaaaa\n2\na aa\na aaa"},{"iden":"sample output 2","content":"2\n\nTwo operations `a` $\\to$ `aaa` $\\to$ `aaaaa` incur a cost of $2$, which is the minimum possible."},{"iden":"sample input 3","content":"a\nz\n1\na abc"},{"iden":"sample output 3","content":"\\-1\n\nNo sequence of operations makes $T=$`z` from $S=$`a`."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}