問題文

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

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

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

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

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

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

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

入力例1

3
soup
peas
ecir

出力例1

1

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

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

入力例2

4
ba
bc
ca
da

出力例2

0

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

入力例3

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

出力例3

12

入力例4

3
aa
xyz
zwx

出力例4

1