AT_abc374_g [ABC374G] Only One Product Name

题目描述

Keyence 的所有商品名均由两个大写英文字母组成。
现已使用了 $N$ 个商品名，第 $i$ 个商品名（$1\leq i\leq N$）为 $S_i$。
由于已使用过的商品名不能再次使用，为了能快速查找过去用过的商品名，决定制作一个 NG 列表。

NG 列表需要满足以下条件：

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

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

输入格式

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

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

输出格式

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

输入输出样例 #1

输入 #1

7
AB
BC
CA
CD
DE
DF
XX

输出 #1

3

输入输出样例 #2

输入 #2

5
AC
BC
CD
DE
DF

输出 #2

2

输入输出样例 #3

输入 #3

6
AB
AC
CB
AD
DB
BA

输出 #3

1

说明/提示

限制条件

• $1\leq N\leq 26^2$
• $N$ 为整数。
• $S_i$ 为仅包含大写英文字母的长度为 $2$ 的字符串。
• $S_1,S_2,\ldots,S_N$ 均互不相同。

样例解释 1

满足条件的 NG 列表例如可以由以下 $3$ 个字符串组成：

• CABCDE
• DF
• XX 这是由 $3$ 个字符串组成的，且不存在由 $2$ 个或更少字符串组成且满足条件的 NG 列表，因此输出 $3$。

样例解释 2

满足条件的 NG 列表例如可以由以下 $2$ 个字符串组成：

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

样例解释 3

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

由 ChatGPT 4.1 翻译