Распознание языка
Детерминированный конечный автомат (ДКА) представляет собой ориентированный мультиграф, вершинами которого являются состояния, а ребра - переходами. Каждый переход ДКА помечен одной буквой. Более того, для каждого состояния s и каждой буквы l существует не более одного перехода, исходящего из s и помеченного как l. ДКА имеет одно стартовое состояние и множество финальных. ДКА определяет язык всех слов, которые могут быть построены в результате записи подряд букв на пути со стартового состояния в некоторое конечное.
Язык задан конечным множеством слов, всегда можно сконструировать ДКА, определяющий этот язык. Слева приведен ДКА распознающий язык из трех слов: fix, foo, ox. Однако этот ДКА имеет 7 состояний, что не оптимально. ДКА справа определяет язык имея всего 5 состояний.
Вам следует найти наименьшее количество состояний в ДКА, который определяет заданный язык.
Входные данные
Первая строка содержит число n (1 ≤ n ≤ 5 000) - количество слов в языке. Каждая из следующих n строк содержит одно слово. Каждое слово содержит от 1 до 30 латинских букв нижнего регистра от "a" до "z". Все слова разные.
Выходные данные
Вывести наименьшее количество состояний ДКА, определяющий заданный на входе язык.