Language Cardinality

A (formal) language is a set of strings. One way to describe a specific language is with ordinary set notation; when the set is large, a grammar can be more convenient.

The grammar we consider here has two parts:

• an initial string, and
• a set of replacement rules, each of the form s1 -> s2, where s1 and s2 are strings.

The language defined by such a grammar is the set of all strings that can be produced by repeatedly replacing an occurrence of s1 with s2 inside the current string, starting from the initial string. The initial string itself belongs to the language, because it is the result of applying zero replacements.

For example, consider the grammar G whose initial string is

"AyB"

and whose replacement rules are

{ "A" -> "ab", "Ay" -> "cdy", "B" -> "w", "B" -> "x" }

Then G generates the language

L = { "AyB", "Ayw", "Ayx", "abyB", "abyw", "abyx", "cdyB", "cdyw", "cdyx" }

Given a grammar G, determine how many different strings the language it generates contains.

The first line contains the initial string.

Each of the following lines contains one replacement rule, one per line, until end-of-file. There are at most 100 replacement rules. Every string in the input consists of between 0 and 10 upper- and lower-case letters and is enclosed in double quotes. The input contains no spaces.

Print a single integer: the number of distinct strings in the language generated by G. If the language contains more than 1000 distinct strings, print Too many. instead.