Longest Word Chain

You are given (n) words, each consisting of exactly 2 lowercase letters. The first word (the word in the first line) is designated as the head of the chain. A valid chain is formed by connecting words such that the second letter of the previous word is equal to the first letter of the next word.

Each word can be used at most once. Your task is to determine the length of the longest chain that can be formed starting from the head word.

Formally, if the words are (w_1, w_2, \dots, w_n) with (w_i = c_{i1}c_{i2}) and the head word is (w_1), then for a chain (w_{i_1}, w_{i_2}, \dots, w_{i_k}) (with (i_1=1)) to be valid, it must satisfy (c_{i_j2} = c_{i_{j+1}1}) for all (1 \leq j < k).

inputFormat

The input begins with an integer (n) representing the number of words. This is followed by (n) lines, each containing a string of 2 lowercase letters. The first word is the designated head of the chain.

outputFormat

Output a single integer, which is the length of the longest valid chain that can be formed following the given rules.

sample

3
ab
bc
cd

3