DFA

Time limit1sMemory limit128 MB

Summary

Given a finite set of words, compute the minimum number of states of a DFA recognizing exactly that language.

Level: Medium7 of 10
Topics: Trie, Dynamic programming, String
Solved: No attempts yet

Problem

A deterministic finite automaton (DFA) is a directed multigraph. Its vertices are called states, and its edges are called transitions.

Every transition of a DFA is labeled with a single letter. Moreover, for each state $s$ and each letter $l$ , there is at most one transition leaving $s$ that is labeled with $l$ .

A DFA has one start state and a set of final states (a subset of all states). A DFA defines a language. A word belongs to this language if and only if there is a path from the start state to some final state such that concatenating the letters on the edges of the path, in order, yields exactly that word.

Given a language with a finite number of words, it is always possible to build a DFA that recognizes exactly that language. For example, one straightforward DFA for the language {fix, foo, ox} has 7 states, but that is not the DFA with the fewest states. The same language can be represented with 5 states, and it cannot be represented with fewer than 5.

Given a language, write a program that computes the minimum number of states needed to build a DFA that recognizes it.

Input

The first line contains the number of words $n$ . ( $1 \le n \le 5000$ )

Each of the next $n$ lines contains one word. Each word consists of lowercase English letters only and has length at most 30. All words in the input are distinct.

Output

Print, on the first line, the minimum number of states needed to build a DFA that recognizes the given language.

Examples7

Example 1
Input
```
3
fix
foo
ox
```
Expected output
```
5
```
Example 2
Input
```
1
a
```
Expected output
```
2
```
Example 3
Input
```
1
abcde
```
Expected output
```
6
```
Example 4
Input
```
2
ab
cb
```
Expected output
```
3
```
Example 5
Input
```
2
ab
ac
```
Expected output
```
3
```
Example 6
Input
```
2
a
ab
```
Expected output
```
3
```
Example 7
Input
```
3
a
b
c
```
Expected output
```
2
```