Only One Product Name

题目描述

所有 KEYENCE 产品名称都由两个大写英文字母组成。
他们已经使用了 $N$ 个产品名称，第 $i$ 个（$1\leq i\leq 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

5
AC
BC
CD
DE
DF

2

6
AB
AC
CB
AD
DB
BA

1

提示

$1\leq N\leq 26^2$ $N$ 是整数。 每个 $S_i$ 是由大写英文字母组成且长度为 $2$ 的字符串。 所有 $S_1,S_2,\ldots,S_N$ 都互不相同。一个满足条件的 NG 列表是由以下三个字符串组成：

$CABCDE$ $DF$ $XX$

这有三个字符串，并且不存在满足条件且字符串数不超过 $2$ 的 NG 列表，因此输出 $3$.
一个满足条件的 NG 列表是由以下两个字符串组成：

$ACDE$ $BCDF$

注意，每个已使用的产品名称可能出现在 NG 列表的多个字符串中或在同一个字符串中多次出现。
例如，仅由 $ABACBADB$ 组成的 NG 列表就满足条件。

标签: AtCoder|abc374G

来源

AtCoder|abc374G