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