Language Recognition#7595
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 and each letter there is at most one transition that leaves and is labeled with . 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 states, which is not optimal. The DFA on the right defines the same language with just states.
Your task is to find the minimum number of states in a DFA that defines the given language.
The first line contains a single integer number (1 \le n \le 5000) - the number of words in the language. It is followed by lines with a word on each line. Each word consists of to lowercase Latin letters from "a" to "z". All words are different.
Write a single integer number - the minimal number of states in a DFA that defines the language from the input.
Example 1
Example 2