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