Description

Given a dictionary that contains $n$ words, define the dictionary order as the order within this dictionary (i.e., the given list order). Select some words and form a word ladder in dictionary order so that the ladder length is maximized.

Rules for the new word ladder:

1. Word transformation: from $w_i$, adding one letter, deleting one letter, or changing one letter can obtain $w_{i+1}$.
2. Dictionary-order chain: $w_1, w_2, \cdots, w_k$ are in dictionary order.

Input Format

The first line contains an integer $n$ ($1 \le n \le 25,000$), the total number of words in the dictionary. The next $n$ lines, in dictionary order, contain $n$ words, one string per line. Each word consists only of lowercase letters, and its length is between $1$ and $16$ inclusive.

Output Format

Output a single integer on one line, the maximum possible length of the word ladder.

9
cat
dig
dog
fig
fin
fine
fog
log
wine

5

Hint

Sample explanation:

A word ladder of length $5$ is: $\texttt{dig}\to \texttt{fig}\to \texttt{fin}\to \texttt{fine}\to \texttt{wine}$.

Translated by ChatGPT 5