#P5032. [Jsoi2014]病毒分类
[Jsoi2014]病毒分类
病毒分类
题目描述
JYY 收集了 种病毒的 DNA 序列,第 种病毒用一个大写英文字母串 表示。病毒按1到 编号。
要把所有病毒分成尽量少的类别,每个病毒恰好属于一个类别。同一类别必须满足下列至少一个条件:
- 全部病毒的前 个字母相同。
- 全部病毒的后 个字母相同。
求最少类别数,并给出一种分类方案。不同类别可以分别采用不同条件。
输入格式
从标准输入读入。第一行两个正整数 。
接下来 行,第 行为字符串 ,保证长度不小于 。
输出格式
向标准输出写出第一行一个整数 ,表示最少类别数。
接下来 行,每行先输出该类病毒数 ,再输出 个病毒编号。全部编号1到 必须恰好出现一次。
存在多个最优方案时,输出任意一种即可。
样例输入
4 1
A
AB
BB
BA
样例输出
2
2 1 2
2 3 4
数据范围
,,。