Yoluxma#10367
Fermer Con və onun həmkarları təsərrüfatlarında iribuynuzlu heyvanlarda COWVID-19 adlı təhlükəli xəstəliyin yayılmasının qarşısını almağa çalışaraq fasiləsiz işləyirlər.
Ümumilikdə nəzarət altında təsərrüfat var, bunlar -dən -ə qədər nömrələnib. Təsərrüfatlar n-1 yol ilə əlaqəlidir, belə ki, təsərrüfat -dən hər hansı bir digər təsərrüfata bəzi yol ardıcıllığı ilə çatmaq mümkündür.
Təəssüf ki, təsərrüfat -də olan inək yeni COWVID-19 üçün müsbət nəticə əldə edib. Hələlik nə bu, nə də digər təsərrüfatlarda heç bir başqa inək yoluxmayıb. Lakin, xəstəliyin son dərəcə yüksək yoluxuculuğunu nəzərə alaraq, fermer Con anlayır ki, hər gün iki hadisədən biri baş verə bilər:
bir təsərrüfatda super-yayılma baş verir, nəticədə həmin təsərrüfatda yoluxmuş inəklərin sayı iki qat artır;
bir yoluxmuş inək bir təsərrüfatdan qonşu təsərrüfata yola düşür.
Fermer Con xəstəliyin yayılmasının nə qədər tez baş verəcəyindən narahatdır. Ona hər təsərrüfatda ən azı bir yoluxmuş inəyin olacağı gün sayını müəyyən etməyə kömək edin.
Birinci sətirdə bir tamam ədəd n~(1 \le n \le 10^5) verilir. Növbəti n - 1 sətirdə iki tamam ədəd və verilir, bunlar təsərrüfatlar və arasında yolla göstərir (1 \le a, b \le n).
Xəstəliyin hər təsərrüfata çatmasını təmin edən minimum gün sayını çıxışa verin.
Nümunəyə uyğun bir hadisə ardıcıllığı belədir:
əvvəlcə təsərrüfat -də yoluxmuş inəklərin sayı iki dəfə iki qat artır və gündən sonra onların sayı olur. Sonra növbəti gün ərzində hər gün təsərrüfat -dən bir yoluxmuş inək təsərrüfat , və -ə keçir. Beləcə, günün sonunda hər təsərrüfatda ən azı bir yoluxmuş inək olacaq.
Nümunə 1