Longest Word Chain

Given a dictionary containing n words, select a subset of these words and arrange them in lexicographical order to form a word chain with the maximum possible length. The chain must satisfy the following rules:

• Word Transformation: For any two consecutive words \(w_i\) and \(w_{i+1}\) in the chain, \(w_{i+1}\) must be obtained from \(w_i\) by exactly one of the following operations:
  • Add one letter,
  • Remove one letter, or
  • Change one letter (substitution).
  In other words, the edit distance between \(w_i\) and \(w_{i+1}\) must be exactly 1.
• Lexicographical Order: The words must appear in increasing lexicographical order, i.e. \(w_1 < w_2 < \cdots < w_k\).

Your task is to determine the maximum length of such a word chain.

inputFormat

The first line contains an integer \(n\) denoting the number of words in the dictionary. The following \(n\) lines each contain a single word.

\(1 \leq n \leq 10^5\) (constraints may vary).

outputFormat

Output a single integer representing the length of the longest word chain satisfying the above rules.

sample

3
a
b
c

3