题目描述

Alice 和 Bob 正在玩一个单词游戏。他们从一个单词列表开始，轮流进行操作。Alice 先手，她从列表中选出一个起始单词。在接下来的每一轮中，当前玩家必须从列表中选择一个单词，该单词的首字母与上一轮另一位玩家所选择的单词的尾字母相同。每个单词只能被使用一次。当某一时刻某位玩家无法选出符合要求的单词时，该玩家输掉游戏。

假设 Alice 和 Bob 都采取最优策略。请问，如果 Alice 首先选择某个单词，那么有多少个单词能够保证 Alice 获胜？

输入格式

输入的第一行包含一个整数 $n$（$1 \leq n \leq 1{,}000$），表示单词的数量。

接下来的 $n$ 行，每行包含一个单词，单词仅由小写字母 a 到 z 组成。每个单词的长度在 $2$ 到 $15$ 之间。所有单词互不相同。所有单词的首字母和尾字母的种类数不超过 $3$ 种。Alice 和 Bob 只能从该列表中选择单词。

输出格式

输出一个整数，表示列表中有多少个单词，当 Alice 首先选择该单词且双方均采取最优策略时，能够保证 Alice 获胜。

3
attic
climb
alpha

2

22
agora
alpha
antic
aorta
apnea
arena
aroma
attic
basic
blurb
china
circa
civic
climb
cobra
cocoa
comic
comma
conic
crumb
cubic
cynic

6

提示

翻译由 DeepSeek V3.2 完成