#P5032. [Jsoi2014]病毒分类

    ID: 4130 传统题 1000ms 256MiB 尝试: 26 已通过: 2 难度: 6 上传者: 标签>难度分类提高图论二分图建模排序与序列处理离散化Kuhn 算法由匹配构造最小点覆盖CF2100

[Jsoi2014]病毒分类

病毒分类

题目描述

JYY 收集了 NN 种病毒的 DNA 序列,第 ii 种病毒用一个大写英文字母串 SiS_i 表示。病毒按1到 NN 编号。

要把所有病毒分成尽量少的类别,每个病毒恰好属于一个类别。同一类别必须满足下列至少一个条件:

  1. 全部病毒的前 kk 个字母相同。
  2. 全部病毒的后 kk 个字母相同。

求最少类别数,并给出一种分类方案。不同类别可以分别采用不同条件。

输入格式

从标准输入读入。第一行两个正整数 N,kN,k。

接下来 NN 行,第 ii 行为字符串 SiS_i,保证长度不小于 kk。

输出格式

向标准输出写出第一行一个整数 CC,表示最少类别数。

接下来 CC 行,每行先输出该类病毒数 ww,再输出 ww 个病毒编号。全部编号1到 NN 必须恰好出现一次。

存在多个最优方案时,输出任意一种即可。

样例输入

4 1
A
AB
BB
BA

样例输出

2
2 1 2
2 3 4

数据范围

N≤5000N\le5000,k≤550k\le550,k≤∣Si∣≤600k\le\lvert S_i\rvert\le600。