G - Only One Product Name 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 600 点

問題文

キーエンスの商品名はすべて 英大文字 2 文字 からなります。
すでに N 個の商品名を使用しており、i 個目 (1\leq i\leq N) の商品名は S_i です。
一度使用した商品名は再び使うことができないので、過去に使用した商品名の一覧がすぐわかるように NG リストを作ることにしました。

NGリストは次の条件をみたす必要があります。

  • 1 つ以上の文字列からなり、各文字列は英大文字のみからなる。
  • すでに使用されている商品名それぞれについて、その商品名を（連続する）部分文字列として含む文字列が 1 つ以上存在する。
  • リスト内のすべての文字列は、すでに使用されている商品名でない長さ 2 の文字列を（連続する）部分文字列として含まない。

NG リストの文字列の数としてあり得る最小の値を求めてください。

制約

  • 1\leq N\leq 26^2
  • N は整数
  • S_i は英大文字のみからなる長さ 2 の文字列
  • 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 リストとしては例えば次の 3 つの文字列からなるようなものが考えられます。

  • CABCDE
  • DF
  • XX

これは 3 つの文字列からなり、2 つ以下の文字列からなり条件をみたす NG リストは存在しないため、 3 を出力します。

入力例 2

5
AC
BC
CD
DE
DF

出力例 2

2

条件をみたす NG リストとしては例えば次の 2 つの文字列からなるようなものが考えられます。

  • ACDE
  • BCDF

すでに使用されている商品名は NG リスト内の複数の文字列に登場したり、同一文字列に複数回含まれたりしていても良いことに注意してください。

入力例 3

6
AB
AC
CB
AD
DB
BA

出力例 3

1

例えば、ABACBADB のみからなる NG リストが条件をみたしています。

Score : 600 points

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.