题目描述

DFA（确定性有限状态自动机）是一个有向图，顶点称为状态，边称为转移。每个转移用一个字母标记。对于每个状态 $s$ 和每个转移 $l$，至多有一个转移从 $s$ 出发且标记为 $l$。DFA 有一个初始状态和若干个结束状态。DFA 定义的语言的单词可以由从开始状态到结束状态的路径上所有的字母连接起来。

图中表示一个语言（包括单词 fix、foo、ox）的 DFA。第一个 DFA 有 $7$ 个状态，它不是最优的。第二个 DFA 定义的是同一个语言，但只有 $5$ 个状态。

给定一个语言，包含有限个单词，求出定义该语言的 DFA 的最少状态数。

输入格式

第一行有一个整数 $n$（$1\leq n\leq 5000$），表示语言的单词数。接下来 $n$ 行，每行一个单词。每个单词由 $1\sim 30$ 个小写字母组成。输入的所有单词互不相同。

输出格式

一个数，定义该语言的 DFA 的最少状态数。

3
fix
foo
ox

5