P7086 [NWRRC 2013] Heavy Chain Clusterization

一组生物学家正在寻找一种治疗病毒性疾病的方法。他们尝试了多种可能对抗病毒抗原的抗体，并选出了在实验中效果最好的 $n$ 种抗体。 每种抗体通过其重链（由氨基酸序列组成）进行识别。 如果满足以下至少一个条件，则这些抗体形成一个相似簇： - 所有重链的 k 前缀（前 $k$ 个氨基酸）相同； - 所有重链的 k 后缀（后 $k$ 个氨基酸）相同。 为了简化未来的研究，生物学家希望将抗体分组为相似簇。 你需要将给定的抗体划分为最少数量的相似簇。

第一行包含两个整数 $n$ 和 $k$ —— 重链的数量和需要一致的氨基酸序列的长度 $(1 \le n \le 5 000 , 1 \le k \le 550)$。 接下来的 $n$ 行包含形成抗体重链的氨基酸序列。每个氨基酸用一个大写的英文字母描述。每个重链至少包含 $k$ 个氨基酸，最多不超过 $550$ 个氨基酸。

输出的第一行必须包含一个整数 —— 最小的相似簇数量。接下来的行必须包含簇的描述，每行一个。 每个描述以 $m_i$ 开头 —— 簇中抗体的数量，接下来是 $m_i$ 个整数 —— 这些抗体的编号。抗体按照输入中出现的顺序编号，从 1 开始。 每个抗体必须恰好出现在一个簇中。

时间限制：2 秒，内存限制：256 MB。 题面翻译由 ChatGPT-4o 提供。