Ağır Zəncir Klasterləşməsi

Bir qrup bioloq viral xəstəliyə qarşı müalicə tapmağa çalışır. Onlar, potensial olaraq viral antigenlərlə mübarizə apara biləcək müxtəlif mənşəli bir çox antikorları sınaqdan keçiriblər və təcrübələr zamanı ən yaxşı işləyən n antikoru seçiblər.

Hər bir antikor öz ağır zənciri ilə - amin turşularının ardıcıllığı ilə müəyyən edilir.

Antikorlar dəsti oxşarlıq klasteri təşkil edir, əgər aşağıdakılardan ən azı biri yerinə yetirilirsə:

• Bütün ağır zəncirlərinin k-prefiksləri (ilk k amin turşuları) eynidir;

• Bütün ağır zəncirlərinin k-suffiksləri (son k amin turşuları) eynidir.

Gələcək tədqiqatları sadələşdirmək üçün bioloqlar antikorları oxşarlıq klasterlərinə qruplaşdırmaq istəyirlər.

Sizə verilmiş antikorları minimum sayda oxşarlıq klasterlərinə bölmək lazımdır.

Giriş

Birinci sətir iki tam ədəd n və k ehtiva edir - ağır zəncirlərin sayı və uyğun gəlməsi lazım olan amin turşularının ardıcıllığının uzunluğu (1 ≤ n ≤ 5000, 1 ≤ k ≤ 550).

Növbəti n sətir antikorların ağır zəncirlərini təşkil edən amin turşularının ardıcıllığını ehtiva edir. Hər bir amin turşusu böyük ingilis hərfi ilə təsvir edilir. Hər bir ağır zəncir ən azı k və ən çox 550 amin turşusu ehtiva edir.

Çıxış

Birinci sətir tək bir tam ədəd ehtiva etməlidir - minimum oxşarlıq klasterlərinin sayı.

Növbəti sətirlər klasterlərin təsvirlərini ehtiva etməlidir, hər biri bir sətirdə.

Hər bir təsvir m[i] ilə başlamalıdır - klasterdəki antikorların sayı və ardınca m[i] tam ədədlər - bu antikorların nömrələri. Antikorlar girişdəki görünüş sırasına görə birdən başlayaraq nömrələnir.

Hər bir antikor dəqiq bir klasterdə olmalıdır.