eolymp
bolt
Try our new interface for solving problems
Məsələlər

Xaç atası

Xaç atası

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB

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 (2n50000) 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.

prb5366.gif

Nümunə

Giriş verilənləri #1
6
1 2
2 3
2 5
3 4
3 6
Çıxış verilənləri #1
2 3
Mənbə 2005 ACM NEERC, Northern Subregional Contest, Санкт-Петербург, Октябрь 29, Задача G