Language Cardinality

Time limit1sMemory limit128 MB

Summary

Count the distinct strings a string-rewriting grammar generates from a start string, printing Too many. if the count exceeds 1000.

Level: Hard8 of 10
Topics: String, BFS, Hash map, Simulation
Solved: No attempts yet

Problem

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.

Input

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.

Output

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.

Examples4

Example 1

Input

"AyB"
"A"->"ab"
"Ay"->"cdy"
"B"->"w"
"B"->"x"

Expected output

Example 2
Input
```
"abc"
```
Expected output
```
1
```
Example 3
Input
```
"AA"
"A"->""
```
Expected output
```
3
```
Example 4
Input
```
"X"
"X"->"a"
"X"->"b"
```
Expected output
```
3
```