#P18694. First Last

    ID: 18030 传统题 1000ms 2048MiB 尝试: 1 已通过: 1 难度: 8 上传者: 标签>CF2400提高+/省选-配对策略必胜/必败状态递推状压 DP记忆化搜索状态维度消除

First Last

First Last

Alice和Bob正在玩单词游戏。他们有一张单词表,并轮流行动。

Alice先手,她可以从表中任选一个单词作为第一个单词。之后的每一轮,当前玩家必须从表中选择一个单词,使它的首字母与对手上一轮所选单词的末字母相同。每个单词最多使用一次。最终某个玩家会无法选择单词,该玩家输掉游戏。

假设双方都采用最优策略,求有多少个表中的单词,在Alice将其作为第一个单词时,能保证Alice获胜。

输入格式

第一行包含一个整数nn(1≤n≤10001\le n\le1000),表示单词数。

接下来nn行,每行包含一个单词,仅由小写英文字母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