#P18694. First Last
First Last
First Last
Alice和Bob正在玩单词游戏。他们有一张单词表,并轮流行动。
Alice先手,她可以从表中任选一个单词作为第一个单词。之后的每一轮,当前玩家必须从表中选择一个单词,使它的首字母与对手上一轮所选单词的末字母相同。每个单词最多使用一次。最终某个玩家会无法选择单词,该玩家输掉游戏。
假设双方都采用最优策略,求有多少个表中的单词,在Alice将其作为第一个单词时,能保证Alice获胜。
输入格式
第一行包含一个整数(),表示单词数。
接下来行,每行包含一个单词,仅由小写英文字母a至z组成,长度为2至15。所有单词互不相同。全部单词的首字母和末字母合起来,至多包含三种不同的字母。Alice和Bob只能选择表中的单词。
注意,这个三种字母的限制只针对首字母和末字母,单词内部可以出现其他小写字母。首尾字母相同的单词合法;不同单词可以具有相同的首尾字母。限制的是同一个单词不能重复使用,字母可以再次访问。
输出格式
输出一个整数,表示当双方都采用最优策略时,Alice可以选作第一个单词并保证自己获胜的单词个数。
样例 1 输入
3
attic
climb
alpha
样例 1 输出
2
样例 2 输入
22
agora
alpha
antic
aorta
apnea
arena
aroma
attic
basic
blurb
china
circa
civic
climb
cobra
cocoa
comic
comma
conic
crumb
cubic
cynic
样例 2 输出
6