İnək təhlükədə (Platin)
Bessi küncə sıxışdırılmış vəziyyətdə uzaq bir fermaya getdi. Bu ferma n tövlədən və n - 1 iki tərəfli tuneldən ibarətdir, belə ki, hər bir tövlə cütü arasında unikal bir yol mövcuddur. Yalnız bir tuneli olan tövlələr çıxış nöqtələridir. Səhər açıldıqda, Bessi hansısa tövlədə peyda olacaq və çıxışa çatmağa çalışacaq.
Bessi yer üzündə göründüyü anda, qanun nümayəndələri onun yerini müəyyən edəcəklər. Bundan sonra, bəzi fermerlər müxtəlif çıxış tövlələrində Bessini tutmağa çalışacaqlar. Fermerlər Bessi ilə eyni sürətlə hərəkət edirlər (yəni, hər addımda hər bir fermer bir tövlədən qonşu tövləyə keçə bilər). Fermerlər həmişə Bessinin harada olduğunu bilirlər və Bessi də həmişə fermerlərin harada olduğunu bilir. Fermerlər Bessini tutacaqlar, əgər hansısa anda bir fermer Bessi ilə eyni tövlədə olarsa və ya Bessi ilə eyni tuneldən keçərsə. Əks halda, Bessi qaçacaq, əgər çıxış tövləsinə fermerlər onu tutmadan çatarsa.
Bessi hansı tövlədə peyda olacağını bilmir. Hər bir n tövlə üçün Bessiyə kömək edin ki, əgər o, orada peyda olarsa, fermerlərin optimal şəkildə çıxış tövlələri arasında paylanacağını nəzərə alaraq, Bessini tutmaq üçün lazım olan minimal fermer sayını müəyyən etsin.
Giriş məlumatları
Birinci sətir n (2 ≤ n ≤ 7 * 10^4) ədədini ehtiva edir. Növbəti n - 1 sətirin hər biri iki tam ədəd ehtiva edir, hər biri 1 .. n aralığında, iki tövlə arasındakı tuneli təsvir edir.
Çıxış məlumatları
n sətir çıxarın, burada i-ci sətir, əgər Bessi i-ci tövlədə peyda olarsa, onu tutmaq üçün lazım olan minimal fermer sayını ehtiva edir.