Oyun
- Amma o bunu necə edir! O, ən hündür şam ağacına çıxır və oradan plan qurur.
- Hə, bağışlayın, nə plan qurur?
"Radio günü"
Qızcığaz Nataşa maraqlı bir oyun üçün meydan hazırlayır. Bu oyunda k komanda iştirak edəcək və hər biri bir və ya bir neçə ağac və ip əldə etməlidir. Hər komanda, öz ağaclarından birindən digərinə keçmək üçün, başqalarının ağaclarını istifadə etmədən, ipdən istifadə etməlidir. İp vasitəsilə bir ağacdan digərinə keçmək mümkündür, əgər ipin uzunluğu onların arasındakı məsafədən az deyilsə.
Bütün iplərin uzunluğu eyni olmalıdır ki, bütün komandalar bərabər şəraitdə olsunlar. Mövcud n ağacı k dəstəyə bölün ki, lazım olan ip uzunluğu mümkün qədər az olsun.
Giriş verilənləri
Giriş məlumatlarının birinci sətirində tam ədədlər n və k - ağacların və komandaların sayı, müvafiq olaraq (1 ≤ k ≤ n ≤ 1000).
Növbəti n sətirdə hər biri üçün iki tam ədəd x_i və y_i - i-ci ağacın koordinatları (-10^4 ≤ x_i, y_i ≤ 10^4).
Çıxış verilənləri
Birinci sətirdə nöqtədən sonra ən azı altı dəqiq rəqəmlə bir real ədəd çıxarın - ipin minimal mümkün uzunluğu. İkinci sətirdə n ədəd 1 ilə k arasında - müvafiq ağacları təyin etmək üçün komandaların nömrələri.
Əgər bir neçə həll varsa, istənilənini çıxarın.