Кластеризація важких ланцюгів
Група біологів працює над створенням ліків від вірусного захворювання. Вони протестували безліч антитіл різного походження, які можуть ефективно боротися з вірусними антигенами, і відібрали n антитіл, що показали найкращі результати в експериментах.
Кожне антитіло визначається своєю важкою ланцюгом — послідовністю амінокислот.
Набір антитіл утворює кластер схожості, якщо виконується хоча б одна з наступних умов:
Перші k амінокислот (префікси) всіх важких ланцюгів однакові;
Останні k амінокислот (суфікси) всіх важких ланцюгів однакові.
Щоб полегшити подальші дослідження, біологи прагнуть згрупувати антитіла в кластери схожості.
Ваше завдання — розділити дані антитіла на мінімальну кількість кластерів схожості.
Вхідні дані
Перша строка містить два цілі числа n і k — кількість важких ланцюгів і довжина послідовності амінокислот, які повинні збігатися (1 ≤ n ≤ 5000, 1 ≤ k ≤ 550).
Наступні n рядків містять послідовності амінокислот, що формують важкі ланцюги антитіл. Кожна амінокислота позначається великою англійською літерою. Кожен важкий ланцюг містить принаймні k і не більше 550 амінокислот.
Вихідні дані
Перша строка повинна містити одне ціле число — мінімальну кількість кластерів схожості.
Наступні рядки повинні містити описи кластерів, по одному на рядок.
Кожен опис починається з m[i] — кількості антитіл у кластері, і продовжується m[i] цілими числами — номерами цих антитіл. Антитіла нумеруються в порядку появи у вхідних даних, починаючи з одиниці.
Кожне антитіло повинно бути присутнім рівно в одному кластері.