Yura dövrü pazlı
Məşhur "Yura Parkı" biologu Din O'Saur, dinozavrın DNT-si olduğunu düşündüyü yeni nümunələr kəşf edib. Köməkçisi Petr Daktil ilə birlikdə bu nümunələri sıralayıb və indi analizə hazırdırlar. Din hesab edir ki, bu dinozavr müəyyən bir xəstəlikdən əziyyət çəkib və bu xəstəlik bəzi hüceyrələrin DNT-sini mutasiyaya uğradıb.
Teoriyasını yoxlamaq üçün o, nümunələrdən ən ehtimal olunan təkamül ağacını müəyyən etməlidir, burada düyünlər DNT nümunələridir. DNT nümunələrinin vaxt məlumatları olmadığı üçün ağacın kökünün harada yerləşdiyi onun üçün əhəmiyyətli deyil.
Din, ən ehtimal olunan təkamül ağacını ən az fərqliliklə olan ağac hesab edir: ağacın fərqliliyi, iki DNT sıranın fərqləndiyi mövqelərin sayı olan kənarların ağırlıqlarının cəmi kimi müəyyən edilir.
Məlumat ağacları üzrə dünya mütəxəssisi olaraq, o, sizdən ən ehtimal olunan təkamül ağacını yenidən qurmağı xahiş edir.
Birinci nümunədə optimal ağac AA - AT - TT - TC olacaq. AA və AT arasında kənarın fərqliliyi 1-ə bərabərdir, çünki AA və AT sırları tam olaraq 1 mövqedə fərqlənir. Digər iki kənarın ağırlıqları da 1-ə bərabərdir. Buna görə də, bütün ağacın fərqliliyi 3-ə bərabərdir. 3-dən az fərqliliyə malik ağac olmadığı üçün bu test üçün təkamül ağacının minimal fərqliliyi 3-dür.
Giriş məlumatları
Birinci sətir n (1 ≤ n ≤ 1000) və k (1 ≤ k ≤ 10) — nümunələrin sayı və onların uzunluğunu göstərən iki tam ədəd ehtiva edir. Növbəti n sətirin hər biri k uzunluğunda və ACTG simvollarından ibarət bir sıranı ehtiva edir.
Çıxış məlumatları
Birinci sətirdə təkamül ağacının minimal fərqliliyini çıxarın. Sonra n − 1 sətir çıxarın, hər biri u, v (0 ≤ u, v < n) iki tam ədəd ehtiva edir, bu da ən ehtimal olunan təkamül ağacında u və v DNT sırları arasında kənarın olacağını göstərir. Bir neçə həll yolu varsa, istənilən birini çıxarın.