#917. 单词接龙

单词接龙

样例下载

题目描述

单词接龙是一个与我们经常玩的成语接龙相类似的游戏。

现在我们有 NN 张卡片,每张卡片上有一个单词。让你从中选取若干张卡片依次摆放成一排,要求后一张卡片上的单词首字母必须与前一张卡片上的单词尾字母相同。

问:你可以拼接成的单词串的长度最长是多少?

输入格式

第一行:一个整数 NN。

接下来 NN 行,每行一个字符串,表示一张卡片上的单词。所有单词均由大写英文字母组成。每个单词的长度不超过 100。不存在两个相同的单词。

输出格式

一个整数,表示可以拼接出的最长单词串的长度。

输入输出样例 #1

输入 #1

5
AB
BDC
BC
CBACD
ACCB

输出 #1

12

数据范围

20% 的数据:1 ≤ N ≤ 10

100% 的数据:1 ≤ N ≤ 16