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