DNA の合成 (DNA synthesizer)

A,T,G,C からなる DNA 鎖が 2 本あるとき, 一方の先頭と, 他方の末尾の部分に 1 文字以上の連続する共通 部分を持つものをつなげて新しい DNA 鎖を合成する方法が開発された. このとき共通部分は一つにまとめ られる. たとえば,TTTATGC と ATGCAAA は，前者の末尾と後者の先頭に共通部分 ATGC を持つので，つ なげて TTTATGCAAA を合成できる. また，AAA を 2 つ用いて，AAAA と AAAAA のどちらも合成するこ とができる．今，新薬開発のために，研究室にあるいくつかの素 DNA 鎖から，ある DNA 鎖を合成したい．

研究室には N 種類の素 DNA 鎖がある．上記の方法で素 DNA 鎖をつなぎあわせて目的の DNA 鎖を合成 するとき, 最小で何本の素 DNA 鎖が必要となるかを求めるプログラムを作成せよ. ただし，素 DNA 鎖の備 蓄には余裕があるので，同じ種類の素 DNA 鎖を何度でも使うことができる．また，全ての採点データにお いて，目的の DNA 鎖を得る素 DNA 鎖の組み合わせが存在する．

標準入力から以下の入力を読み込め．

• 1 行目には整数 N が書かれている．
• 2 行目には，A,T,G,C からなる文字列が書かれており, 目的の DNA 鎖を表す.
• 続く N 行は，1 行につき 1 つの A,T,G,C からなる文字列が書かれており，それぞれ 1 つの素 DNA 鎖 を表す．重複する素 DNA 鎖は存在しない．

標準出力に必要となる素 DNA の本数の最小値を表す 1 つの整数を出力せよ.

• 素 DNA 鎖の種類数 N は 50,000 以下である．
• 合成したい DNA 鎖の長さは 150,000 以下である．
• 素 DNA 鎖の長さは 20 以下である．