Description

一组生物学家正在寻找一种治疗病毒性疾病的方法。他们尝试了多种可能对抗病毒抗原的抗体，并选出了在实验中效果最好的 $n$ 种抗体。

每种抗体通过其重链（由氨基酸序列组成）进行识别。

如果满足以下至少一个条件，则这些抗体形成一个相似簇：

• 所有重链的 k 前缀（前 $k$ 个氨基酸）相同；
• 所有重链的 k 后缀（后 $k$ 个氨基酸）相同。

为了简化未来的研究，生物学家希望将抗体分组为相似簇。

你需要将给定的抗体划分为最少数量的相似簇。

Input Format

第一行包含两个整数 $n$ 和 $k$ —— 重链的数量和需要一致的氨基酸序列的长度 $(1 \le n \le 5 000 , 1 \le k \le 550)$。

接下来的 $n$ 行包含形成抗体重链的氨基酸序列。每个氨基酸用一个大写的英文字母描述。每个重链至少包含 $k$ 个氨基酸，最多不超过 $550$ 个氨基酸。

Output Format

输出的第一行必须包含一个整数 —— 最小的相似簇数量。接下来的行必须包含簇的描述，每行一个。

每个描述以 $m_i$ 开头 —— 簇中抗体的数量，接下来是 $m_i$ 个整数 —— 这些抗体的编号。抗体按照输入中出现的顺序编号，从 1 开始。

每个抗体必须恰好出现在一个簇中。

4 1
AA
AB
BB
BA

2
2 1 2
2 3 4

3 2
ABA
BAB
XY

3
1 1
1 2
1 3

Hint

时间限制：2 秒，内存限制：256 MB。

题面翻译由 ChatGPT-4o 提供。