{"problem":{"name":"Replace","description":{"content":"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$\\","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc261_g"},"statements":[{"statement_type":"Markdown","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$.\n\n## Constraints\n\n*   $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.\n\n## Input\n\nInput 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$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc261_g","tags":[],"sample_group":[["ab\ncbca\n3\na b\nb ca\na efg","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."],["a\naaaaa\n2\na aa\na aaa","2\n\nTwo operations `a` $\\to$ `aaa` $\\to$ `aaaaa` incur a cost of $2$, which is the minimum possible."],["a\nz\n1\na abc","\\-1\n\nNo sequence of operations makes $T=$`z` from $S=$`a`."]],"created_at":"2026-03-03 11:01:14"}}