103746: [Atcoder]ABC374 G - Only One Product Name

Problem Statement

All KEYENCE product names consist of two uppercase English letters.
They have already used $N$ product names, the $i$-th of which $(1\leq i\leq N)$ is $S_i$.
Once a product name is used, it cannot be reused, so they decided to create an NG (Not Good) list to quickly identify previously used product names.

The NG list must satisfy the following conditions.

• It consists of one or more strings, each consisting of uppercase English letters.
• For each already used product name, there exists at least one string in the list that contains the name as a (contiguous) substring.
• None of the strings in the list contain any length-$2$ (contiguous) substring that is not an already used product name.

Find the minimum possible number of strings in the NG list.

Constraints

• $1\leq N\leq 26^2$
• $N$ is an integer.
• Each $S_i$ is a string of length $2$ consisting of uppercase English letters.
• All $S_1,S_2,\ldots,S_N$ are distinct.

Input

The input is given from Standard Input in the following format:

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

Output

Print the minimum possible number of strings in the NG list.

Sample Input 1

7
AB
BC
CA
CD
DE
DF
XX

Sample Output 1

3

One NG list satisfying the conditions is the one consisting of the following three strings:

• CABCDE
• DF
• XX

This has three strings, and there is no NG list satisfying the conditions with $2$ or fewer strings, so print $3$.

Sample Input 2

5
AC
BC
CD
DE
DF

Sample Output 2

2

One NG list satisfying the conditions is the one consisting of the following two strings:

• ACDE
• BCDF

Note that each used product name may appear in multiple strings in the NG list or multiple times within the same string.

Sample Input 3

6
AB
AC
CB
AD
DB
BA

Sample Output 3

1

For example, an NG list consisting only of ABACBADB satisfies the conditions.

问题陈述

所有KEYENCE产品名称均由两个大写英文字母组成。
他们已经使用了$N$个产品名称，其中第$i$个$(1\leq i\leq N)$是$S_i$。
一旦产品名称被使用，它就不能再被使用，因此他们决定创建一个NG（不好）列表，以快速识别之前使用的产品名称。

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

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

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

约束条件

• $1\leq N\leq 26^2$
• $N$是一个整数。
• 每个$S_i$是一个由两个大写英文字母组成的字符串。
• 所有的$S_1,S_2,\ldots,S_N$都是不同的。

输入

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

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

输出

打印NG列表中字符串的最小可能数量。

示例输入1

7
AB
BC
CA
CD
DE
DF
XX

示例输出1

3

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

• CABCDE
• DF
• XX

这个列表有三个字符串，并且不存在满足条件的由2个或更少字符串组成的NG列表，所以打印3。

示例输入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列表满足条件。