Longest Suffix Chain

Given a list of strings, your task is to determine the length of the longest sequence (chain) of strings in which each string (except the first) is a suffix of the previous string. You are allowed to reorder the strings arbitrarily, but each string can be used at most once.

In mathematical terms, if the sequence is \(s_1, s_2, \dots, s_k\), then for every \(1 \leq i < k\), string \(s_{i+1}\) must be a suffix of string \(s_i\) (i.e. \(s_i \text{ ends with } s_{i+1}\)).

You need to output the maximum possible length \(k\) of such a chain.

Example:
For the input strings: ["a", "ba", "aba", "x", "y"], one valid chain is "aba" → "ba" → "a", so the answer is 3.

inputFormat

The input is read from standard input (stdin). The first line contains an integer \(n\) \( (1 \leq n \leq 10^5)\) representing the number of strings. This is followed by \(n\) lines, each containing a non-empty string.

outputFormat

Output a single integer to standard output (stdout): the length of the longest suffix chain possible among the given strings.

5
a
ba
aba
x
y

3