UOJ Logo 黑暗爆炸OJ

DARKBZOJ

#2559. [Poi1998] AB-words Abs

统计 下载数据

Description

每一个由字母a和b组成的序列(或是空序列),称为ab-word。如果X=[x1,..,xn]是一个ab-word并且有i,j是整数(1<=i<=j<=n),那么X[i..j]表示由字母xi,..,xj组成的X的字符串。如果一个ab-word X=[x1,..xn] 中,字母a的个数等于字母b的个数,并且对于任何i=1,...,n,字符串X[1,i]中,字母a 与b至少都个数相等,那么,我们称这个ab-word X=[x1,..xn] 为好的。
现在,我们给出两个好的ab-words之间类似的归纳定义。
每两个空的ab-words(字符串内无字母)是相似的
两个非空的好ab-words, X=[x1,...,xn] 和Y=[y1,..,ym] 是相似的,如果他们的长度相等(n=m),并且以下的条件有一个满足:
1、 x1=y1, xn=yn 和X[2..n-1] 和Y[2..n-1] 是相似的 ab-words并且他们都是好的
2、 存在i(1<=i<=n),使X[1..i]和 X[i+1..n]是好的ab-words,并且
a、Y[1..i], Y[i+1..n]是好的ab-words,X[1..i]与Y[1..i]相似,X[i+1..n] 与 Y[i+1..n]相似,或者
b、Y[1..n-i], Y[n-i+1..n]是好的ab-words ,X[1..i] 与 Y[n-i+1..n] 相似X[i+1..n] 与Y[1..n-i]相似.
一个好的ab-words 的非空集合s的多样性的水平是ab-words的最大个数,他满足:s中任意一对w1和w2,w1不相似于w2

Input

写出以下一个程序:
读出元素s;
算出集合s的多样性的水平;

在输入文件的首行有集合S(1<=n<=1000)的元素个数;在接下来的n行里是集合S的元素,诸如ab-words(一行一个单词);每一个ab-word的首字母是每行的首记号。字符串中两个连续字母之间没有空隙;每一个ab-word的长度是[1..200]中的一个整数。

Output

Sample Input

首单行应该记下一个整数-S多样性的等级。

Sample Output



3
aabaabbbab
abababaabb
abaaabbabb



Hint

Source