CF191A.Dynasty Puzzles

The ancient Berlanders believed that the longer the name, the more important its bearer is. Thus, Berland kings were famous for their long names. But long names are somewhat inconvenient, so the Berlanders started to abbreviate the names of their kings. They called every king by the first letters of its name. Thus, the king, whose name was Victorious Vasily Pupkin, was always called by the berlanders VVP.

In Berland over its long history many dynasties of kings replaced each other, but they were all united by common traditions. Thus, according to one Berland traditions, to maintain stability in the country, the first name of the heir should be the same as the last name his predecessor (hence, the first letter of the abbreviated name of the heir coincides with the last letter of the abbreviated name of the predecessor). Berlanders appreciate stability, so this tradition has never been broken. Also Berlanders like perfection, so another tradition requires that the first name of the first king in the dynasty coincides with the last name of the last king in this dynasty (hence, the first letter of the abbreviated name of the first king coincides with the last letter of the abbreviated name of the last king). This tradition, of course, has also been always observed.

The name of a dynasty is formed by very simple rules: we take all the short names of the kings in the order in which they ruled, and write them in one line. Thus, a dynasty of kings "ab" and "ba" is called "abba", and the dynasty, which had only the king "abca", is called "abca".

Vasya, a historian, has recently found a list of abbreviated names of all Berland kings and their relatives. Help Vasya to find the maximally long name of the dynasty that could have existed in Berland.

Note that in his list all the names are ordered by the time, that is, if name A is earlier in the list than B, then if A and B were kings, then king A ruled before king B.

古代贝尔兰德人认为，名字越长，其拥有者就越重要。因此，贝尔兰德的国王以超长的名字而闻名。但长名字使用起来颇为不便，于是贝尔兰德人开始缩写国王们的名字：他们用国王全名中每个单词的首字母来称呼国王。例如，名为“Victorious Vasily Pupkin”的国王，总是被贝尔兰德人称为“VVP”。

在贝尔兰德漫长的历史中，许多王室王朝相继更替，但它们均遵循着共同的传统。根据其中一项贝尔兰德传统，为维持国家稳定，继承人的名字（即其全名中的第一个单词）必须与其前任国王的姓氏（即其全名中的最后一个单词）相同（因此，继承人缩写名的首字母必须与前任国王缩写名的末字母相同）。贝尔兰德人珍视稳定，因此这一传统从未被打破。此外，贝尔兰德人崇尚完美，另一项传统则要求：一个王朝中首位国王的名字必须与该王朝末位国王的姓氏相同（因此，首位国王缩写名的首字母必须与末位国王缩写名的末字母相同）。当然，这一传统也始终被严格遵守。

一个王朝的名称由非常简单的规则构成：我们将该王朝所有国王的缩写名按其统治顺序依次拼接成一个字符串。例如，由缩写名为“ab”和“ba”的两位国王组成的王朝，其王朝名称为“abba”；而仅有一位缩写名为“abca”的国王所构成的王朝，其王朝名称即为“abca”。

历史学家瓦夏最近发现了一份贝尔兰德所有国王及其亲属的缩写名列表。请帮助瓦夏找出在贝尔兰德历史上可能存在的最长王朝名称。

注意：该列表中所有名字均按时间顺序排列，即若名字 A 在列表中排在 B 之前，则当 A 和 B 均为国王时，国王 A 的统治时间早于国王 B。

The first line contains integer n (1 ≤ n ≤ 5·105) — the number of names in Vasya's list. Next n lines contain n abbreviated names, one per line. An abbreviated name is a non-empty sequence of lowercase Latin letters. Its length does not exceed 10 characters.

第一行包含一个整数 $n$（$1 \leq n \leq 5 \cdot 10^5$）——表示瓦夏名单中姓名的数量。接下来的 $n$ 行每行包含一个缩写姓名，共 $n$ 个缩写姓名。每个缩写姓名是一个非空的小写拉丁字母序列，其长度不超过 10 个字符。

Print a single number — length of the sought dynasty's name in letters.

If Vasya's list is wrong and no dynasty can be found there, print a single number 0.

输出一个数字——所求王朝名称的字母长度。

如果瓦西娅的列表有误，其中不存在任何王朝，则输出一个数字 0。

In the first sample two dynasties can exist: the one called "abcca" (with the first and second kings) and the one called "abccba" (with the first and third kings).

In the second sample there aren't acceptable dynasties.

The only dynasty in the third sample consists of one king, his name is "c".

在第一个样例中，可以存在两个王朝：一个名为“abcca”（包含第一位和第二位国王），另一个名为“abccba”（包含第一位和第三位国王）。

在第二个样例中，不存在合法的王朝。

第三个样例中唯一的王朝仅包含一位国王，其名字为“c”。