仅一个商品名

题目描述

KEYENCE 的所有商品名都由两个大写英文字母构成。

他们已经使用了 $N$ 个商品名，其中第 $i$ 个（$1 \le i \le N$）为 $S_i$。

商品名一旦使用便不能重复使用，因此他们决定制作一个 NG（Not Good）列表，以便快速识别已使用过的商品名。

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

• 由一个或多个由大写英文字母构成的字符串组成。
• 对于每个已使用的商品名，列表中都至少有一个字符串包含该商品名作为（连续的）子串。
• 列表中的任意字符串都不包含任何「不是已使用商品名」的长度为 $2$ 的（连续）子串。

求 NG 列表中字符串数量的最小可能值。

输入格式

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

$N$
$S_1$
$S_2$
$\vdots$
$S_N$

输出格式

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

样例

7
AB
BC
CA
CD
DE
DF
XX

3

一个满足条件的 NG 列表由以下三个字符串组成：

• CABCDE
• DF
• XX

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

5
AC
BC
CD
DE
DF

2

一个满足条件的 NG 列表由以下两个字符串组成：

• ACDE
• BCDF

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

6
AB
AC
CB
AD
DB
BA

1

例如，仅由 ABACBADB 组成的 NG 列表满足条件。

数据范围

• $1 \le N \le 26^2$
• $N$ 为整数
• 每个 $S_i$ 是长度为 $2$、由大写英文字母构成的字符串
• 所有 $S_1, S_2, \ldots, S_N$ 互不相同