8494: BZOJ4494:[Neerc2013 North]heavy

Memory Limit:512 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

一群生物学家正在找一个病毒性疾病的解药。他们已经尝试了许多来源不同的抗体, 它 们都有可能消灭病毒抗原。他们选出了 n 种在试验中看起来最有效的抗体。 每种抗体通过它们的重链(一种氨基酸)来识别。 符合以下任意一个条件的一群抗体,形成一个“相似群体”: 1. 它们的重链中的 K-前缀全部都是相同的 2. 它们的重链中的 K-后缀全部都是相同的 为了简化将来的研究,生物学家想把所有抗体分成几个“相似群体”。因此你需要将给 定的抗体分成数量最少的几个“相似群体”。


输入格式

第一行包含两个整数 n 和 k ,分别表示重链的数量和需要相同的重链的长度。 以下 n 行每行包括一个重链。每个重链是用一串大写英文字母表示,并且长度在 k 与550 之间。


输出格式

第一行包括一个整数,最少的相似群数目。 以下每行描述一个相似群: 描述以 mi 开都,表示在该群内抗体的数量。后面跟着 mi 个整数,表示这些抗体的编号。 编号按输入的顺序从小到大。每个抗体只能出现在一个群内。


样例输入

4 1
AA
AB
BB
BA

样例输出

22

提示

N<=5000,K<=300


题目来源

没有写明来源

加入题单

上一题 下一题 算法标签: