Delegasiya (Platin)
Fermer Conun ferması, hər hansı bir otlaqdan digərinə keçilə biləcək şəkildə n otlaqdan və n - 1 yoldan ibarətdir. Yəni, ferma bir ağac strukturuna malikdir. Lakin 28 il ərzində ağaclarla bağlı alqoritmik problemlərlə məşğul olduqdan sonra, Con ağac formasında olan fermanın çox mürəkkəb olduğunu düşündü. O, hesab edir ki, alqoritmik məsələlər yollar üzərində daha sadədir.
Onun planı yollar çoxluğunu bir neçə yola bölmək və bu yolların məsuliyyətini öz layiqli fermasına həvalə etməkdir. O, yolların sayından çox, bu yolların mümkün qədər uzun olmasını təmin etmək istəyir ki, heç bir fermer asimptotik olaraq səmərəsiz alqoritmlərdən qaça bilməsin!
Fermer Cona, yolların uzunluğu ən azı k olan yollar şəklində bölünə biləcəyi ən böyük müsbət tam ədəd k-ni müəyyən etməyə kömək edin.
Giriş Məlumatları
Birinci sətir tək tam ədəd n (2 ≤ n ≤ 10^5) ehtiva edir. Növbəti n - 1 sətirin hər biri a və b tam ədədlərini ehtiva edir, bu da a və b zirvələri arasında kənarı göstərir. Həm a, həm də b 1 .. n aralığında yerləşir.
Çıxış Məlumatları
k dəyərini çıxış edin.
Nümunə
Mümkün yollardan biri belədir: 2−1−6−7−8, 3−1−4−5.