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
Language:
Language Recognition
Time Limit: 5000MSMemory Limit: 65536K
Total Submissions: 1882Accepted: 504Special Judge

Description

Deterministic Final-State Automaton (DFA) is a directed multigraph whose vertices are called states and edges are called transitions. Each DFA transition is labeled with a single letter. Moreover, for each state s and each letter l there is at most one transition that leaves s and is labeled with l. DFA has a single starting state and a subset of final states. DFA defines a language of all words that can be constructed by writing down the letters on a path from the starting state to some final state.

Given a language with a finite set of words it is always possible to construct a DFA that defines this language. The picture on the left shows such DFA for the language consisting of three words: fix, foo, ox. However, this DFA has 7 states, which is not optimal. The DFA on the right defines the same language with just 5 states.

Your task is to find the minimum number of states in a DFA that defines the given language.

Input

The first line of the input file contains a single integer number n (1 ≤ n5 000) — the number of words in the language. It is followed by n lines with a word on each line. Each word consists of 1 to 30 lowercase Latin letters from “a” to “z”. All words in the input file are different.

Output

Write to the output file a single integer number — the minimal number of states in a DFA that defines the language from the input file.

Sample Input

#13
fix
foo
ox
#24
a
ab
ac
ad

Sample Output

#15
#23

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