Using sed

sed is a Linux utility that replaces occurrences of a string $\alpha$ with another string $\beta$ in the strings given as input; here, each input string is a single line of a file. sed performs the following two steps:

1. Mark non-overlapping occurrences of $\alpha$ in the input string. (Occurrences of $\alpha$ may overlap one another in the text, but the marked ones must not overlap.) When there is more than one way to choose a non-overlapping set of occurrences, choose the leftmost ones.
2. Replace every marked $\alpha$ with $\beta$ simultaneously. All other characters are left unchanged.

For example, if $\alpha$ is aa, $\beta$ is bca, and the input string is aaxaaa, then running sed gives bcaxbcaa (it cannot be aaxbcaa or bcaxabca). Running sed again on bcaxbcaa gives bcaxbcbca.

You are given $n$ replacement rules $(\alpha_i, \beta_i)$ for $i = 1, 2, \ldots, n$, an initial string $\gamma$, and a target string $\delta$. Using sed, you want to transform $\gamma$ into $\delta$ with the minimum number of replacement operations.

A single rule $(\alpha_i, \beta_i)$, as described above, replaces all non-overlapping (leftmost) occurrences of $\alpha_i$ in the current string with $\beta_i$ at the same time; this counts as one operation. Each rule may be used any number of times, including zero.

The input consists of several test cases. Each test case has the following format:

n
α1 β1
α2 β2
...
αn βn
γ
δ

Here $n$ is the number of replacement rules. Each $\alpha_i$ and $\beta_i$ are separated by a space and satisfy $1 \le |\alpha_i| < |\beta_i| \le 10$, where $|s|$ denotes the length of the string $s$. For all $i \ne j$, $\alpha_i \ne \alpha_j$. Also $n \le 10$ and $1 \le |\gamma| < |\delta| \le 10$. All strings consist of lowercase letters only. The last line of the input contains a single $0$.

For each test case, output the minimum number of replacement operations needed to transform $\gamma$ into $\delta$. If $\gamma$ cannot be transformed into $\delta$, output $-1$.