#3734. 「COCI 2015.11」SAVEZ

题目描述

题目译自 COCI 2015-2016 CONTEST #2 T4 「SAVEZ」。

有一个秘密行星 S4 居住着一种奇特的动物，它们的学名是 Loda。Savez 协会派出了一个由 Henrik 将军领导的小组来研究 Loda。Henrik 发现，Loda 有心灵传输的能力，他想在他的军队里雇佣他们。

一只 Loda 由 $N$ 个字符串组成，其中第 $i$ 个字符串记为 $x_i$。研究表明，Loda 能进行的心灵传输次数取决于组成它的字符串的一个特殊子序列（不一定是连续的）。字符串 $x_i$ 和 $x_j$ ($i<j$) 都可以在该子序列中，当且仅当字符串 $x_j$ 以 $x_i$ 开头并以 $x_i$ 结尾。一只 Loda 可以进行的心灵传输次数是组成它的字符串的合法的最长子序列的长度，而你就需要确定它可以进行心灵传输的次数。

输入格式

第一行一个整数 $N$，表示组成某一只 Loda 的字符串总数。

接下来 $N$ 行，每行一个仅由大写英文字母构成的字符串 $x_i$，表示构成这一只 Loda 的字符串。

输出格式

一行一个整数，表示这只 Loda 可以进行心灵传输的次数。

---

样例 1

输入

5
A
B
AA
BBB
AAA

输出

3

一个最长的子序列为 A AA AAA。

---

样例 2

输入

5
A
ABA
BBB
ABABA
AAAAAB

输出

3

---

样例 3

输入

6
A
B
A
B
A
B

输出

3

子序列中的字符串允许相等，因此一个最长的子序列为 A A A 或 B B B。

---

数据范围与提示

对于 $100\%$ 的数据，$1\le N \le 2\times 10^6$，$1\le |x_i| \le 2\times 10^6$，保证 $\sum |x_i|\le10^6$。