Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
北京大学《ACM-ICPC竞赛训练》暑期课面向全球招生。容量有限,报名从速!
Language:
Language Cardinality
Time Limit: 1000MSMemory Limit: 65536K
Total Submissions: 1231Accepted: 261

Description

A (formal) language is a set of strings. One way to define a particular langauge is using ordinary set notation. Alternatively, some form of grammar may be more convenient for representing large sets. The UW grammar in which we are interested has two parts:
  • An initial string
  • A set of replacement rules of the form s1 -> s2 where s1 and s2 are strings

The language defined by this grammar is the set of all strings that can be generated by repeatedly replacing s1 by s2 within the initial string. For example, consider the grammar G consisting of the initial string

"AyB"

and the replacement rules
{"A"->"ab", "Ay"->"cdy", "B"->"w", "B"->"x"} .

G generates the language

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

Given a UW grammar G, compute how many different strings there are in the language generated by G.

Input

The first line of input contains the initial string. The second and subsequent lines contain the replacement rules, one per line, terminated by end-of-file. There are at most 100 replacement rules. Each input string contains between 0 and 10 upper and lower case letters, and is enclosed in quotes. There are no spaces in the input.

Output

Output consists of a single integer, the number of distinct strings in the language generated by G. If there are more than 1000 distinct strings, print "Too many." instead.

Sample Input

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

Sample Output

9

Source

[Submit]   [Go Back]   [Status]   [Discuss]

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator