← 返回题目列表

AtCoder · code_thanks_festival_14_qualb_h

H. 知鸟游戏

中文机器翻译题面 查看原题

問題文

您最近沉迷于一款稍微特殊的Shiritori游戏,并购买了“Shiritori基本套装”,其中包含一些英文单词(注)。

Shiritori游戏的规则如下。

  • 知鸟游戏中评论中可以使用的词语是预先确定的,其他词语不能在评论中使用。 但是,当使用英文单词时,您可以说相反的版本。
  • 英文单词一旦使用,以后就不能再使用(即使说出相反的版本,也不能使用原来的单词)。
  • 学生第一次可以自由选择英语单词和说话。
  • 2 第一个话语后说出的英语单词的第一个字母必须与前一个话语的最后一个字母匹配。
  • 当你尝试说话时,如果没有符合条件的英语单词,Shiritori立即结束。

通常,Shiritori 是由多人玩的,但如果您喜欢独处,您会想独自玩,目标是在一场 Shiritori 游戏中使用所有英语单词并完成游戏。 然而,您足够聪明,意识到无论您多么努力,仅使用 Shiritori 基础套装中包含的英语单词您可能无法实现您的目标。

因此,我决定单独购买一些额外的英语单词,并仅使用这些单词和“Shiritori Basic Set”中包含的英语单词来玩 Shiritori 游戏,以实现我的目标。请注明您必须购买的最少英文单词数。

幸运的是,你生活在一个任何英语单词都有大量可用的世界,你可以根据需要购买任意数量的单词。

(注)这里的英文单词是指字母表中的小写字母(a-z)长度 假设您引用的是字符串 2 ~ 20 。请注意,这与英语单词的实际定义相去甚远。


入力

输入是按以下格式从标准输入给出的。

N
w_1
w_2
:
w_N
  • 1 第一行显示“Shiritori Basic Set”中包含的英语单词数量。 在 N (1 ≦ N ≦ 100,000) 。
  • 2 从行 N 行中,给出了“Shiritori基本集”中包含的英语单词的信息。这几天之一 代表第 i 行中,i 个英文单词 写入 w_i (2 ≦ |w_i| ≦ 20) 。 w_i 是一个小写字母 ( 仅a-z)。
  • 所有单词保证彼此不同。还可以保证一个单词的反转永远不会与另一个单词匹配。 在线

出力

1 上打印您必须购买的最少英文单词数。不要忘记最后的换行符。


入力例1

3
soup
peas
ecir

出力例1

1

无法单独使用“Shiritori Basic Set”中包含的所有英语单词。

例如,这个词 通过购买 sugar 通过购买``soup→peas→sugar→rice(最后 rice 是 仅由 ecir ),您可以使用所有单词完成Shiritori游戏并实现您的目标。


入力例2

4
ba
bc
ca
da

出力例2

0

例如,ab→bc→ca→ad如果您玩Shiritori游戏,则无需购买额外的英文单词。在这个例子中,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