Təhlükədə inək (Qızıl)#10424
Nəhayət küncə sıxışdırılan Bessi uzaq bir fermada gizlənib. Ferma tövlədən və onlar arasında n-1 ikitərəfli tuneldən ibarətdir, hər hansı iki tövlə arasında yalnız bir yol mövcuddur. Yalnız bir tunellə bağlı olan hər bir tövlə çıxış sayılır. Səhər açılanda Bessi tövlələrdən birində yer üzünə çıxacaq və çıxışa çatmağa çalışacaq.
Ancaq Bessi yer üzünə çıxan kimi, qanun gözətçiləri onun dəqiq yerini müəyyən edə biləcəklər. Bundan sonra bir neçə fermer müxtəlif çıxış-tövlələrdən hərəkətə başlayıb Bessini tutmağa çalışacaqlar. Fermerlər Bessi ilə eyni sürətlə hərəkət edirlər, yəni hər zaman vahidi ərzində hər fermer bir tövlədən qonşu tövləyə keçə bilər. Fermerlər istənilən anda Bessinin harada olduğunu bilirlər, Bessi isə istənilən anda fermerlərin harada olduğunu bilir. Əgər hər hansı bir anda fermerlərdən biri Bessi ilə eyni tövlədə olarsa və ya onunla eyni tuneldən keçərsə, fermerlər Bessini tutmuş olurlar. Əksinə, əgər Bessi hər hansı bir fermer tərəfindən tutulmazdan əvvəl çıxış-tövləyə çata bilərsə, qaçmış sayılır.
Bessi uğur qazanma şansına əmin deyil, çünki bu, qanun gözətçilərinin neçə fermer cəlb edə biləcəyindən asılıdır. Məlumdur ki, Bessi tövləsindən yer üzünə çıxacaq. Fermerlərin çıxış-tövlələr arasında optimal şəkildə bölüşdürüldüyünü fərz edərək, Bessini tutmaq üçün tələb olunan minimum fermer sayını tapmağa kömək edin.
Birinci sətirdə iki tam ədəd və k~(2 \le n \le 10^5, 1 \le k \le n) verilir. Sonrakı n-1 sətirdən hər biri a_i və b_i~(1 \le a_i, b_i \le n) tövlələri arasındakı tuneli təsvir edən iki tam ədəd a_i və b_i ehtiva edir.
Bessini tutmağı zəmanət altına almaq üçün tələb olunan minimum fermer sayını çap edin.
Nümunə 1