시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 23 5 4 28.571%

문제

Little Adrian is a fan of rhyme. He believes that two words rhyme if and only if their longest common suffix is as long as the longer of the two words, or shorter than the longer word by 1. In other words, A and B rhyme if and only if it holds . LCS(A, B) ≥ max(|A|, |B|) - 1

One day, while reading a collection of short stories, he decided to compose the longest possible sequence of words such that each two consecutive words rhyme. Each word from the sequence can appear only once.

Adrian has grown tired of this task, so he decided to go back to reading, and is asking you to solve this task instead of him. 

입력

The first line of input contains the integer N (1 ≤ N ≤ 500 000).

Each of the following N lines contains one word consisting of lowercase letters of the English alphabet. All words are mutually distinct, and their total length is at most 3 000 000. 

출력

You must output the length of the longest sequence. 

예제 입력

4
honi
toni
oni
ovi

예제 출력

3

예제 입력 2

5
ask
psk
krafna
sk
k

예제 출력 2

4

예제 입력 3

5
pas
kompas
stas
s
nemarime

예제 출력 3

1

힌트