Worms#541

Worms

3 seconds

64 megabytes

Medium

Biologists are studying a certain, interesting kind of worm. Each worm can be represented as a sequence of cells of different types. When a worm is born, it consists of a single cell. Every day, exactly $1$ cell of the entire worm grows and turns into $2$ cells. It is easy to determine the age of such a worm: it is one less than the number of cells the worm has.

During a worm's growth, a cell does not change into any $2$ arbitrary cells; each worm has a set of "growth rules" (encoded in its DNA). A growth rule can be expressed as $A \Rightarrow B C$ A \Rightarrow BC, where $A$ , $B$ and $C$ are uppercase letters ( $A$ – $T$ ), representing different types of the worm's cells. The rule $A \Rightarrow B C$ A \Rightarrow BC means that in one day, any single cell $A$ can grow into the two adjacent cells $B C$ , in that order. Note that the rule $I \Rightarrow J K$ I \Rightarrow JK is different from $I \Rightarrow K J$ I \Rightarrow KJ. Different worms may have different sets of growth rules.

Now, worms have surprised scientists. For some unknown reason, some worms have mutated into a new kind of specimen. This new type of worm has the same properties, except that during its growth, several parts of its body can grow simultaneously. That is, every day any (at least one, at most all) of its cells may grow, and each growing cell will grow into exactly $2$ cells (following the growth rules).

As a result, it is no longer trivial to determine the age of the worm. In fact, the exact age of some worms cannot be determined. For example, if a worm has growth rules: $A \Rightarrow B C$ A \Rightarrow BC, $B \Rightarrow A C$ B \Rightarrow AC, $C \Rightarrow A B$ C \Rightarrow AB, and the worm's current cell structure is $A C A B$ , then the worm might be either $2$ or $3$ days old ( $A \Rightarrow B C \Rightarrow A C A B$ A \Rightarrow BC \Rightarrow ACAB or $A \Rightarrow B C \Rightarrow A C C \Rightarrow A C A B$ A \Rightarrow BC \Rightarrow ACC \Rightarrow ACAB). Your task is to determine the youngest possible age of a given mutated worm.

Input

There will be multiple worms for examination in the input. Each worm's data set begins with an integer $N$ ( $1 \leq N \leq 80$ 1\le N \le 80), the number of growth rules. The next $N$ lines each contain $3$ uppercase letters ( $A$ – $T$ ), representing a growth rule for the current worm. The first cell can grow into (and be replaced by) the second and third cells, in that order, during the growth process. That is, the line:

$A B C$

means $A \Rightarrow B C$ A \Rightarrow BC is a growth rule for the current worm.

The next (and last) line of each worm's data set contains a string of uppercase letters ( $A$ – $T$ ). This line represents the current cell structure of the worm. Every worm in the input will have at least $1$ and at most $50$ cells.

The last worm will be followed by a line with a single $0$ .

Output

For each worm, if the worm can be grown into the given cell sequence with the given growth rule set (starting with any single cell), print the minimum age, in days, of the worm as an integer on its own line. If the worm cannot be grown into the given cell sequence with the rule set (starting with any single cell), print the number $- 1$ on its own line. Do not print blank lines between outputs.

Examples

Example 1