Adrian là một fan cuồng vần điệu. Anh ấy tin rằng hai từ có vần điệu khi và chỉ khi hậu tố chung ~(LCS)~ của chúng có độ dài bằng độ dài từ dài hơn trong hai từ hoặc ngắn hơn độ dài từ dài trong hai từ một chữ cái. Nói cách khác, ~A~ và ~B~ được cho là có vần khi và chỉ khi ~LCS (A, B) ≥ max (|A|, |B|) - 1~.
Một ngày nọ, trong lúc đang đọc một tập truyện ngắn, anh quyết định tạo ra chuỗi dài nhất có thể có sao cho hai từ liên tiếp nhau đều có vần. Mỗi từ trong chuỗi chỉ được xuất hiện một lần.
Adrian đã cảm thấy mệt mỏi với nhiệm vụ này, vì vậy anh ấy quyết định tiếp tục đọc truyện, bạn hãy giải quyết nhiệm vụ này giúp anh ta.
Input
Dòng đầu tiên chứa số nguyên ~N~ ~(1 \leq N \leq 5 \times 10^5)~.
~N~ dòng tiếp theo mỗi dòng chứa một từ gồm các chữ cái viết thường. Các từ phân biệt đôi một và tổng độ dài của chúng tối đa ~3 \times 10^6~.
Output
Ghi ra độ dài của chuỗi dài nhất.
Sample Input 1
4
honi
toni
oni
ovi
Sample Output 1
3
Sample Input 2
5
ask
psk
krafna
sk
k
Sample Output 2
4
Giải thích ví dụ 2: ask-psk-sk-k
Sample Input 3
5
pas
kompas
stas
s
nemarime
Sample Output 3
1
Giải thích ví dụ 3: Không có hai từ nào có vần điệu với nhau.
Subtask
- ~30\%~ số test có ~N \le 18~
- ~70\%~ số test còn lại không có điều kiện gì thêm
Bình luận