该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

T3. 单词接龙

题目描述

单词接龙是一个经典的文字游戏。给定 $N$ 个互不相同的单词，你需要从中选出尽可能多的单词，排成一个序列，使得：

• 序列中第一个单词可以是任意一个单词；
• 序列中相邻的两个单词，前一个单词的最后一个字母必须等于后一个单词的第一个字母；
• 每个单词最多只能使用一次（但同一个单词如果在列表中多次出现——本题保证不会发生——则可以分别使用）。

请你计算：满足条件的最长单词序列使用了多少个单词。

输入格式

第一行一个整数 $N$，表示单词数量。

接下来 $N$ 行，每行一个字符串，表示一个单词。单词仅由小写英文字母 a-z 组成。

输出格式

输出一行一个整数，表示最长单词序列中单词的个数。

样例

样例 #1

输入样例(t3.in)

6
apple
elephant
tiger
rabbit
table
egg

输出样例(t3.out)

6

解释：全部 $6$ 个单词恰好可以串成一条链： apple → elephant → tiger → rabbit → table → egg

首尾字母依次为：a→e, e→t, t→r, r→t, t→e, e→g，满足相邻条件。

样例 #2

输入样例

4
abc
cde
efg
cba

输出样例

4

解释：cba → abc → cde → efg 使用了全部 $4$ 个单词。

样例 #3

输入样例

4
dog
god
cat
tiger

输出样例

2

解释：可能的链有 dog → god（$d→g, g→d$），或 cat → tiger（$c→t, t→r$）。最长长度为 $2$。注意 dog → god → dog 不可行，因为 dog 已被使用过一次。

数据范围与提示

对于 $100\%$ 的数据，$1 \le N \le 15$，每个单词长度不超过 $20$，单词仅由小写字母组成，且 $N$ 个单词互不相同。