Score : $600$ points

问题陈述

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

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

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

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

以上为大语言模型 kimi 翻译，仅供参考。

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.