[ABC374] G - Only One Product Name

G - Only One Product Name

Time Limit: 2 sec / Memory Limit: 1024 MB

分数: 600 分

题面

所有KEYENCE产品名称都由两个大写英文字母组成。
他们已经使用了个产品名称，第个产品名称为。
一旦使用了一个产品名称，就不能重新使用，因此他们决定创建一个NG（不好）列表，以便快速识别先前使用过的产品名称。

NG列表必须满足以下条件。

• 它由一个或多个字符串组成，每个字符串由大写英文字母组成。
• 对于每个已使用的产品名称，列表中至少存在一个字符串，其中包含该名称作为一个（连续的）子串。
• 列表中的字符串不包含任何非已使用产品名称的长度为的（连续的）子串。

找出NG列表中可能的最小字符串数。

限制条件

• 为整数。
• 每个是由两个大写英文字母组成的长度为的字符串。
• 所有均不相同。

---

输入

输入以以下格式从标准输入给出：

输出

输出NG列表中可能的最小字符串数。

---

输入样例 1

7
AB
BC
CA
CD
DE
DF
XX

输出样例 1

3

满足条件的一个NG列表包括以下三个字符串：

• CABCDE
• DF
• XX

这有三个字符串，不存在包含个或更少字符串的满足条件的NG列表，因此输出为。

---

输入样例 2

5
AC
BC
CD
DE
DF

输出样例 2

2

满足条件的一个NG列表包括以下两个字符串：

• ACDE
• BCDF

请注意，每个已使用的产品名称可能会出现在NG列表中的多个字符串中或在同一字符串中多次出现。

---

输入样例 3

6
AB
AC
CB
AD
DB
BA

输出样例 3

1

例如，只由ABACBADB构成的一个NG列表满足条件。