题目描述

一个形式语言是一个字符串的集合。定义特定语言的一种方法是使用常规的集合表示法。此外，某种形式的语法可能更方便表示大型集合。我们感兴趣的 UW 语法包含两部分：

1. 一个初始字符串
2. 一组替换规则，形式为 $s_1 \rightarrow s_2$，其中 $s_1$ 和 $s_2$ 是字符串

该语法生成的语言是通过在初始字符串中反复将 $s_1$ 替换为 $s_2$ 所生成的所有字符串的集合。例如，考虑语法 $G$，其初始字符串为

$"AyB"$

替换规则为

$\{"A" \rightarrow "ab",\ "Ay" \rightarrow "cdy",\ "B" \rightarrow "w",\ "B" \rightarrow "x"\}$

$G$ 生成的语言为

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

给定一个 UW 语法 $G$，计算由 $G$ 生成的语言中有多少不同的字符串。

输入

第一行输入包含初始字符串。第二行及后续行包含替换规则，每行一条，以文件结束符终止。最多有 $100$ 条替换规则。每个输入字符串包含 $0$ 到 $10$ 个大写和小写字母，并用引号括起来。输入中没有空格。

输出

输出为一个整数，表示由 $G$ 生成的语言中不同字符串的数量。如果不同字符串的数量超过 $1000$，则输出 $"Too\ many."$。

示例输入

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

示例输出

9  

来源

Waterloo local $2000.09.23$