Yoluxma

Fermer Con və onun həmkarları, fermalarında COWVID-19 adlı qorxunc mal-qara xəstəliyinin yayılmasını nəzarətdə saxlamaq üçün fasiləsiz çalışırlar.

Onlar birlikdə $1$-dən $n$-ə qədər nömrələnmiş $n$ fermaya nəzarət edirlər. Fermalar $n-1$ yol ilə birləşdirilib, belə ki, hər hansı bir fermaya $1$ nömrəli fermadan bəzi yol ardıcıllığı ilə çatmaq mümkündür.

Təəssüf ki, $1$ nömrəli fermadakı inək COWVID-19 üçün müsbət nəticə verdi. Digər fermalardakı inəklər hələ xəstələnməyib. Lakin, xəstəliyin yoluxucu təbiətini bilən fermer Con hər növbəti gün aşağıdakı əlverişsiz hadisələrdən birinin baş verəcəyini proqnozlaşdırır:

• Bir fermada "super yayılma" hadisəsi COWVID-19 ilə yoluxmuş inəklərin sayını ikiqat artırır;

• COWVID-19 ilə yoluxmuş bir inək bir fermadan qonşu fermaya yolla hərəkət edir.

Fermer Con xəstəliyin nə qədər sürətlə yayıla biləcəyindən narahatdır. Ona kömək edin ki, hər fermada ən azı bir inəyin xəstələnə biləcəyi minimal gün sayını müəyyən etsin.

Giriş verilənləri

Birinci sətir $n(1\le n\le 10^5)$ tək tam ədədini ehtiva edir. Növbəti $n-1$ sətirin hər biri fermalar $a$ və $b$ arasında yolu təsvir edən iki tam ədəd ehtiva edir. Həm $a$, həm də $b$ $\mathrm{1...}n$ diapazonundadır.

Çıxış verilənləri

Xəstəliyin hər fermaya çatması üçün minimal gün sayını çıxarın.

Nümunələr

Bu nümunəyə uyğun olan mümkün hadisələr ardıcıllığından biri belədir: $1$ nömrəli fermadakı xəstə inəklərin sayı ikiqat artır, sonra yenidən ikiqat artır, belə ki, iki gündən sonra $1$ nömrəli fermada $4$ olur. Növbəti $3$ gün ərzində xəstə inək $1$ nömrəli fermadan müvafiq olaraq $2,3$ və $4$ nömrəli fermalara gedir. $5$ gün sonra hər fermada ən azı $1$ xəstə inək olacaq.