Maksimum Axın#11163
Fermer Ceyms öz anbarındakı tövlə arasında süd daşımaq üçün n - 1 borudan ibarət yeni sistem qurmuşdur, tövlələr -dən -ə qədər rahatlıq üçün nömrələnmişdir. Hər boru tövlələr cütünü birləşdirir və istənilən iki tövlə arasında borularla yalnız bir yol mövcuddur.
FC tövlə cütü arasında süd nasos edir. -ci belə cüt üçün sizə iki tövlə, s_i və t_i verilir ki, bunlar südün vahid zamanda bir vahid sürətlə nasos edildiyi yolun uc nöqtələridir. FC narahatdır ki, bəzi tövlələr çoxlu südün onlardan keçməsi səbəbindən həddindən artıq yüklənə bilər, çünki bir tövlə südün nasos edildiyi yoldan bir çoxunun aralıq nöqtəsi ola bilər.
Ona istənilən tövlədən keçən maksimum süd miqdarını müəyyən etməkdə kömək edin. Əgər süd s_i-dən t_i-yə olan yol boyunca nasos edilirsə, o zaman bunun hər iki uc tövlədən, s_i və t_i-dən, həmçinin bu yol üzərində onların arasında yerləşən hər bir tövlədən keçdiyi hesab olunur.
Birinci sətirdə iki tam ədəd verilir: n~(2 \le n \le 50000) və k~(1 \le k \le 10^5).
Sonrakı n - 1 sətirin hər birində və y~(x \ne y) tövlələrini birləşdirən boruyu təsvir edən iki tam ədəd verilir.
Sonrakı sətirin hər birində süd nasos edilən yolun uc tövlələrini müəyyən edən iki tam ədəd və verilir.
Anbardakı istənilən tövlədən keçən maksimum süd miqdarını göstərən bir tam ədəd çap edin.
Nümunə 1