P16073 [ICPC 2023 NAC] First Last

Alice 和 Bob 正在玩一个单词游戏。他们从一个单词列表开始，轮流进行操作。Alice 先手，她从列表中选出一个起始单词。在接下来的每一轮中，当前玩家必须从列表中选择一个单词，该单词的首字母与上一轮另一位玩家所选择的单词的尾字母相同。每个单词只能被使用一次。当某一时刻某位玩家无法选出符合要求的单词时，该玩家输掉游戏。 假设 Alice 和 Bob 都采取最优策略。请问，如果 Alice 首先选择某个单词，那么有多少个单词能够保证 Alice 获胜？

输入的第一行包含一个整数 $n$（$1 \leq n \leq 1{,}000$），表示单词的数量。 接下来的 $n$ 行，每行包含一个单词，单词仅由小写字母 `a` 到 `z` 组成。每个单词的长度在 $2$ 到 $15$ 之间。所有单词互不相同。所有单词的首字母和尾字母的种类数不超过 $3$ 种。Alice 和 Bob 只能从该列表中选择单词。

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

翻译由 DeepSeek V3.2 完成