Xaç atası
Xaç atası
Keçən il Çikaqoda çox sayda qanster basqınları və qəribə ölüm halları baş vermişdir. Polis rəisi bütün bu cinayətlərdən bezmişdir və mafiya liderlərini həbs etmək qərarına gəldi.
Bədbəxtçilikdən, Çikaqodakı mafiya strukturu kifayət qədər mürəkkəb idi. Mafiyanın n nəfərdən təşkil olunduğu məlum idi. Polis bir müddət onlara nəzarət etdi və kimin kim ilə ünsiyyətdə olduğunu müəyyənləşdirdi. Bu məlumatlara əsaslanaraq polis rəisi müəyyən etdi ki, mafiya iyerarxiyasını ağac formasında təsvir etmək olar. Mafiyanın başçısı, xaç atası ağacın kökündə yerləşir. Əgər mafiya üzvünü ağacın təpəsi kimi təsvir edəriksə, onda ona birbaşa tabe olanlar bu təpənin uşaqları sayılırlar. Sirr saxlama qaydalarına görə qansterlər yalnız özlərinə birbaşa tabe olanlarla və rəisləri ilə ünsiyyətə olurlar.
Mövcud əlaqə şəbəkəsinin olmasına baxmayaraq hər bir ünsiyyətdə olan cütlükdə kimin rəis, kimin də tabelikdə olduğunu bilmir. Yəni yalnız kimin xaç atası olmasının müəyyən olmadığı istiqamətlənməmiş əlaqə ağacı məlumdur.
Xaç atası mafiyanın digər üzvlərinə daha çox nəzarət etmək istəyir. Bu informasiyaya əsaslanaraq polis rəisi ehtimal etdi ki, xaç atası o şəxsdir ki, əlaqə ağacından onu çıxartdıqda əmələ gələn ən böyük əlaqəlilik komponentinin ölçüsü ən kiçik olsun. Polisə potensial xaç atalarını tapmaqda kömək edin.
Giriş verilənləri
İlk sətir mafiyada olan adamların n (2 ≤ n ≤ 50000) sayını ehtiva edir. Mafiyanın bütün üzvləri 1-dən n-ə qədər ədədlərlə nömrələnir. Sonra n - 1 sayda a[i]
, b[i]
ədədlər cütlüyü verilir. Burada a[i]
qanqsteri b[i]
qanqsteri ilə ünsiyyətdə olduğunu ifadə edir. Qanqsterlərin ünsiyyət şəbəkəsinın ağac təşkil etdiyinə zəmanət verilir.
Çəxəş verilənləri
Yeganə sətirdə artan ardıcıllıqda xaç atası ola biləcək bütün qanqsterlərin nömrəsini verin. Veriləcək ədədləri boşluqla ayırın.
Nümunə
6 1 2 2 3 2 5 3 4 3 6
2 3