Mal-qara fermaları#5298
Kənd Maksoyaroslavetsdə inəklər adətən çəmənliklərdə otlayır. Çəmənliklər cığırlarla birləşdirilmişdir və hər çəmənlikdə ən azı bir inək otlayır. Hər bir çəmənlik cütü üçün bu cığırlar vasitəsilə birindən digərinə gedən yeganə bir yol mövcuddur. Hər cığır ikitərəflidir və bütün cığırların uzunluğu eynidir.
Kəndin baş fermeri öz inəkləri üçün çəmənliklərdə tövlə tikmək istəyir. Axşam hər inək öz çəmənliyinə ən yaxın olan tövləyə qayıdacaq (əgər bir neçə tövləyə məsafə eynidirsə, inək istənilənini seçə bilər). Maksimum inəyin tövləyə çatmaq üçün keçməli olduğu cığır sayı minimum olacaq şəkildə tövlələri yerləşdirmək lazımdır.
Birinci sətirdə iki tam ədəd və (2 \leq n \leq 50000, 1 \leq k \leq n) — müvafiq olaraq çəmənliklərin və tövlələrin sayı verilir. Sonrakı n-1 sətirin hər birində iki tam müsbət ədəd və verilir, bu da və çəmənliklərinin bir cığırla birləşdirildiyini göstərir. Çəmənliklər -dən nömrələnir.
Birinci sətirdə — inəyin tövləyə çatmaq üçün keçməli olduğu maksimal cığır sayını yazın. İkinci sətirdə müxtəlif tam ədəd — tövlələrin tikilməli olduğu çəmənliklərin nömrələrini yazın. Əgər optimal həllər bir neçədirsə, onlardan istənilən birini çıxışda göstərə bilərsiniz.
Nümunə 1