Problem
Eine Wortkette der Länge n nennen wir die Wortfolge w1, w2, ..., wn so, dass für 1 ≤ i ≤ n das Wort wi das eigene Präfix des Wortes wi + 1 ist.
Denken Sie daran, dass das Wort u der Länge k als eigenes Präfix des Wortes v der Länge l bezeichnet wird, wenn l > k und die ersten k Buchstaben des Wortes v mit dem Wort u übereinstimmen.
Es gibt viele Wörter S = {s1, s2, ..., sm}. Finden Sie die maximale Länge einer Wortkette, die Sie mit (möglicherweise nicht allen) Wörtern dieser Menge erstellen können.
Eingabe
Die erste Zeile der Eingabedatei enthält eine ganze Zahl m(1 ≤ m ≤ 255). Jede der nachfolgenden m-Zeilen enthält ein Wort aus der Menge S.
Alle Wörter sind nicht leer, haben eine Länge von mehr als 255 Zeichen und bestehen nur aus Kleinbuchstaben des lateinischen Alphabets.
Ausgabe
Geben Sie in der Ausgabedatei die Antwort auf die Aufgabe aus.
| Eingabe |
Ausgabe |
|
3
a
ab
abc
|
3 |
|
5
a
ab
bc
bcd
add
|
2 |