← 返回题目列表

Codeforces · 191/A

A. 王朝谜题

中文机器翻译题面 查看原题

古代贝兰德人相信,名字越长,其持有者越重要。因此,贝尔兰国王以其长名字而闻名。但长名字有些不方便,因此贝尔兰德人开始缩写国王的名字。他们用名字的第一个字母来称呼每一位国王。因此,这位名叫胜利瓦西里·普普金(Victorious Vasily Pupkin)的国王总是被伯兰德人称为“VVP”。

在贝尔兰,在其悠久的历史中,许多王朝的国王互相更替,但他们都因共同的传统而团结在一起。因此,根据贝尔兰的传统,为了维护国家的稳定,继承人的名字应该与其前任的姓氏相同(因此,继承人缩写名称的第一个字母与前任缩写名称的最后一个字母一致)。伯兰德人崇尚稳定,所以这一传统从未被打破。另外贝尔兰德人喜欢完美,所以另一个传统要求王朝第一位国王的名字与该王朝最后一位国王的姓氏一致(因此,第一位国王的缩写名称的第一个字母与最后一位国王缩写名称的最后一个字母一致)。当然,这一传统也一直被遵守。

王朝的名称由非常简单的规则组成:我们按照国王统治的顺序取出所有国王的简称,并将它们写在一行中。因此,国王“ab”和“ba”的王朝称为“abba”,而只有国王“abca”的王朝称为“abca”。

历史学家瓦夏(Vasya)最近发现了一份所有贝尔兰国王及其亲属的缩写名单。帮助瓦夏找到贝尔兰可能存在的王朝的最长名称。

请注意,在他的列表中,所有名字都是按时间排序的,也就是说,如果名字 A 在列表中早于 B,那么如果 A 和 B 都是国王,那么国王 A 在国王 B 之前统治。

输入

第一行包含整数 n (1 ≤ n ≤ 5·105) — Vasya 列表中的姓名数量。接下来的 n 行包含 n 个缩写名称,每行一个。缩写名称是小写拉丁字母的非空序列。其长度不超过10个字符。

输出

打印一个数字 — 所查找王朝名称的字母长度。

如果 Vasya 的列表是错误的并且在那里找不到王朝,则打印一个数字 0。

示例

输入 #1

3
abc
ca
cba

输出 #1

6

输入 #2

4
vvp
vvp
dam
vvp

输出 #2

0

输入 #3

3
ab
c
def

输出 #3

1

注意

在第一个样本中,可以存在两个王朝:一个称为“abcca”(具有第一和第二个国王),另一个称为“abccba”(具有第一和第三个国王)。

在第二个样本中,没有可接受的王朝。

第三个样本中唯一的王朝由一位国王组成,他的名字是“c”。