← 返回题目列表

Codeforces · 590/E

E. 生日

中文机器翻译题面 查看原题

今天是小达莎的生日——她今年 8 岁了!这次,她的n个亲朋好友都给了她一条丝带,上面写着问候语,结果发现,所有的问候语都不一样。达莎收集了所有丝带,并决定扔掉其中一些,以使剩下的套装变得时尚。如果某条丝带上写的问候语不是另一条丝带上写的另一条问候语的子串,生日女孩就会认为一套丝带很时尚。让我们回想一下,字符串 s 的子串是 s 的连续段。

帮助达莎保留尽可能多的丝带,这样她就可以向她所有的朋友吹嘘它们。 Dasha 无法旋转或翻转丝带,也就是说,每个问候语都可以以输入中给出的单一方式读取。

输入

输入的第一行包含整数n (1 ≤ n ≤ 750)——Dasha的亲友人数。

接下来的 n 行中的每一行都包含一个问候语。每个问候语仅由字符“a”和“b”组成。

所有问候语的总长度不会超过 10 000 000 个字符。

输出

在第一行打印时尚套装的最大尺寸。在第二行中,打印其中涉及的色带数量,假设它们按照它们在输入中出现的顺序从 1 到 n 编号。如果有几套最大尺寸的时尚套装,请打印其中任意一套。

示例

输入 #1

5
abab
aba
aabab
ababb
bab

输出 #1

2
2 5

注意

在示例中,保留丝带 3 和 4 的答案也被认为是正确的。