Longest Word Chain Sequence

You are given a list of words. Your task is to determine the length of the longest sequence of words in which every word (except the first) starts with the last letter of the previous word. Formally, given words \(w_1, w_2, \dots, w_n\), you should find the maximum \(k\) such that there exists a sequence of distinct indices \(i_1, i_2, \dots, i_k\) with the property that for each \(1 \leq j .

Note:

• Each word can be used at most once.
• If no chain can be formed, the answer is 1 (a single word is a valid chain).

Example 1:

Input:
6
apple
elephant
tiger
ram
monkey
yak
Output:
6

</p>

Example 2:

Input:
4
cat
dog
giraffe
elephant
Output:
3

</p>

inputFormat

The input is read from standard input (stdin) and has the following format:

 n
 word1
 word2
 ...
 wordn

Where n (an integer) represents the number of words, and the following n lines contain one word per line.

outputFormat

Output to standard output (stdout) a single integer representing the length of the longest valid word chain.

## sample

6
apple
elephant
tiger
ram
monkey
yak

6