P1481 Demon Password

As soon as Feng Zhi Zi stepped into his exam room, ... Huahua: Ta-da~~ I am the Queen of Charm — Huahua!! ^^ (grand entrance, confetti, flowers) Feng Zhi Zi: Ugh... (a killer stare) State the problem! Or else... -_-###

Huahua: ... Eh~~ such a chill~~ We are going to solve the demons’ password problem (self-indulgent: maybe some demons will even use ciphers to write love letters to me and Caichong; oh ho ho, of course I’ll get more of them ^_^). The demon clan now uses a new kind of password system. Each password is a given list of English words containing only lowercase letters, and each word has at least $1$ letter and at most $75$ letters. If, in a list consisting of one or more words, every word except the last is contained by the next word, that is, the previous word is a prefix of the next word, then the list is called a “word chain.” For example, the following words form a word chain: - `i`. - `int`. - `integer`. But the following words do not form a word chain: - `integer`. - `intern`. Your task is to pick some words from the given list to form the longest word chain, i.e., the chain that contains the most words. Count its number of words; that number is the password. Feng Zhi Zi: So the password is the number of words in the longest word chain...

The first line contains the number of words $N$ ($1 \le N \le 2000$). Each of the next $N$ lines contains one word, in lexicographic order, with no duplicates.

Output a single line with one integer, the password.

Translated by ChatGPT 5