code thanks festival 2014 B日程(オープンコンテスト)

H - しりとりゲーム


Time limit時間制限 : 2sec / Memory limitメモリ制限 : 256MB

問題文

あなたは最近、ほんの少し特殊なしりとりゲームにハマっており、いくつかの英単語(注)が含まれる「しりとり基本セット」を購入しました。

しりとりゲームのルールは以下の通りです。

  • しりとりゲームでの発言に用いることのできる単語を予め決めておき、それ以外の単語は発言に用いることができないものとする。 ただし、英単語を用いる際、それを反転させたものを代わりに発言してもよい。
  • 一度用いた英単語は今後使用できない(反転したものを発言した場合も、元の単語は使用できなくなる)。
  • 初回は、自由に英単語を選んで発言する。
  • 2 回目以降に発言する英単語は、その先頭文字と直前の発言の末尾文字が一致していなければならない。
  • 発言しようとしたときに、条件を満たす英単語が存在しなかった場合、その場でしりとりは終了する。

普通、しりとりは複数人でプレイするものですが、孤独を好むあなたは全ての英単語を余すことなく一回のしりとりゲームで使用しゲームを終えることを目標に、一人遊びを行おうと思っています。 しかし、賢いあなたは「しりとり基本セット」に含まれる英単語だけではどう頑張っても目標を達成できない可能性があることに気づきました。

そこで、追加の英単語をいくつか単品で購入して、それらと「しりとり基本セット」に含まれる英単語のみを用いてしりとりゲームを行い、目標を達成することとしました。あなたが購入しなければならない英単語の最小数を答えてください。

あなたが住んでいる世界では、幸運なことに任意の英単語が潤沢な数売られており、必要な数だけ購入することができます。

(注) ここでいう英単語とは、アルファベット小文字(a-z)のみから構成される 長さ 220 の文字列のことを指すとします。実際の英単語の定義とはかけ離れていることに注意してください。


入力

入力は以下の形式で標準入力から与えられる。

N
w_1
w_2
:
w_N
  • 1 行目には、「しりとり基本セット」に含まれる英単語の数 N (1 ≦ N ≦ 100,000) が与えられる。
  • 2 行目から N 行には、「しりとり基本セット」に含まれる英単語の情報が与えられる。そのうち i 行目には、i 番目の英単語を表す w_i (2 ≦ |w_i| ≦ 20) が書かれている。 w_i はアルファベット小文字(a-z)のみから構成される。
  • 全ての単語は互いに異なることが保障されている。また、ある単語を反転させたものが別の単語と一致することがないことも保障されている。

出力

1 行目に、あなたが購入しなければならない英単語の最小数を出力せよ。末尾の改行を忘れないこと。


入力例1

3
soup
peas
ecir

出力例1

1

「しりとり基本セット」に含まれる英単語だけでは、それらを余すことなく使用し尽くすことはできません。

そこで、例えば単語 sugar を買うことによって、「souppeassugarrice」 (最後の riceecir を反転したもの)というように、全ての単語を使ってしりとりゲームを終えることができ、目標を達成できます。


入力例2

4
ba
bc
ca
da

出力例2

0

一例として、「abbccaad」というようにしりとりゲームを行えば、英単語追加購入する必要はありません。この例では、bada を反転して使っています。


入力例3

13
ab
cd
ef
gh
ij
kl
mn
op
qr
st
uv
wx
yz

出力例3

12

入力例4

3
aa
xyz
zwx

出力例4

1

Submit提出する