Dil tanıma

Deterministik sonlu avtomat (DSA) istiqamətli multiqrafdır, burada zirvələr vəziyyətlər, kənarlar isə keçidlərdir. Hər bir DSA keçidi bir hərflə işarələnir. Bundan əlavə, hər bir s vəziyyəti və hər bir l hərfi üçün s vəziyyətindən çıxan və l kimi işarələnmiş ən çox bir keçid mövcuddur. DSA bir başlanğıc vəziyyətə və bir neçə son vəziyyətə malikdir. DSA başlanğıc vəziyyətdən müəyyən bir son vəziyyətə qədər olan yolda ardıcıl hərflərin yazılması nəticəsində qurula bilən bütün sözlərin dilini müəyyən edir.

Dil sonlu sözlər çoxluğu ilə verildikdə, bu dili müəyyən edən DSA qurmaq həmişə mümkündür. Solda üç sözdən ibarət dili tanıyan DSA verilmişdir: fix, foo, ox. Lakin bu DSA 7 vəziyyətə malikdir ki, bu da optimal deyil. Sağdakı DSA cəmi 5 vəziyyətə malik olmaqla dili müəyyən edir.

Sizə verilən dili müəyyən edən DSA-nın ən az vəziyyət sayını tapmaq lazımdır.

Giriş məlumatları

Birinci sətir n (1 ≤ n ≤ 5 000) - dildəki sözlərin sayını ehtiva edir. Növbəti n sətirin hər biri bir söz ehtiva edir. Hər bir söz 1-dən 30-a qədər kiçik latın hərflərindən "a" ilə "z" arasında ibarətdir. Bütün sözlər fərqlidir.

Çıxış məlumatları

Verilən dili müəyyən edən DSA-nın ən az vəziyyət sayını çıxış edin.