DFA

결정적 유한 오토마타(DFA)는 방향 간선을 가진 멀티그래프이다. 정점은 상태(state), 간선은 전이(transition)라고 부른다.

DFA의 모든 전이에는 글자 하나가 적혀 있다. 또한 각 상태 $s$와 각 글자 $l$에 대해, $s$에서 나가면서 글자 $l$이 적힌 전이는 최대 한 개만 존재한다.

DFA에는 시작 상태가 하나 있고, 최종 상태들의 집합(상태 전체의 부분집합)이 있다. DFA는 하나의 언어를 정의한다. 어떤 단어가 이 언어에 속하려면, 시작 상태에서 출발하여 어떤 최종 상태에 도달하는 경로가 있어야 하고, 그 경로의 간선에 적힌 글자들을 순서대로 이어 붙인 것이 그 단어와 같아야 한다.

단어의 개수가 유한한 언어가 주어지면, 이 언어를 정확히 인식하는 DFA를 항상 만들 수 있다. 예를 들어 언어 {fix, foo, ox}를 단순하게 나타낸 DFA는 상태가 7개이지만, 이는 상태 수가 가장 적은 DFA가 아니다. 같은 언어를 상태 5개로도 나타낼 수 있으며, 5개보다 적은 상태로는 이 언어를 나타낼 수 없다.

언어가 주어졌을 때, 이 언어를 인식하는 DFA를 만드는 데 필요한 상태의 최소 개수를 구하는 프로그램을 작성하시오.

첫째 줄에 단어의 개수 $n$이 주어진다. ($1 \le n \le 5000$)

다음 $n$개의 줄에는 단어가 한 줄에 하나씩 주어진다. 각 단어는 알파벳 소문자로만 이루어져 있으며 길이는 최대 30이다. 입력으로 주어지는 모든 단어는 서로 다르다.

첫째 줄에 주어진 언어를 인식하는 DFA를 만드는 데 필요한 상태의 최소 개수를 출력한다.