Suffix-Replacement Grammars

As computer programmers, you have likely heard about regular expressions and context-free grammars. These are rich ways of generating sets of strings over a small alphabet, also known as formal languages. There are other, more esoteric ways of generating languages, such as tree-adjoining grammars, context-sensitive grammars, and unrestricted grammars. This problem uses a new method for generating a language: a suffix-replacement grammar.

A suffix-replacement grammar consists of a starting string S and a set of suffix-replacement rules. Each rule has the form X → Y, where X and Y are equal-length strings of alphanumeric characters. The rule means that if the suffix (the rightmost characters) of the current string is X, you can replace that suffix with Y. The rules may be applied any number of times.

For example, suppose there are 4 rules: A → B, AB → BA, AA → CC, and CC → BB. The string AA can be transformed into BB with three rule applications: AA → AB (using A → B), then AB → BA (using AB → BA), and finally BA → BB (using A → B again). It can also be done with two applications: AA → CC, then CC → BB.

You must write a program that takes a suffix-replacement grammar and a string T, and determines whether the starting string S can be transformed into T. If it is possible, the program must also find the minimum number of rule applications required.

The input consists of several test cases. Each case starts with a line containing two equal-length alphanumeric strings S and T (each between 1 and 20 characters long, separated by whitespace), and an integer NR (0 to 100), the number of rules. Each of the next NR lines contains two equal-length alphanumeric strings X and Y (each between 1 and 20 characters long, separated by whitespace), meaning that X → Y is a rule of the grammar. All strings are case-sensitive. The last test case is followed by a line containing a single period.

For each test case, print the case number (starting with 1) followed by the minimum number of rule applications needed to transform S into T. If the transformation is not possible, print No solution. Follow the required format exactly.