Bir hissə
Goa Krallığı, n adadan (1-dən n-ə qədər nömrələnmiş) ibarət bir şəbəkədir və bu adalar n - 1 ikitərəfli körpü ilə birləşdirilib. Bu şəbəkə ağac strukturuna malikdir. Bəzi adalarda qiymətli xəzinələr var və Luffy bütün adalardakı xəzinələri tapmağa çalışır.
Xəzinə axtarışını asanlaşdırmaq üçün o, yerli tacirdən bir detektor aldı. Detektor hər adadan ən yaxın xəzinəyə olan məsafəni (körpülərin sayı) göstərməli idi; lakin o, xarab oldu və bunun əvəzinə hər adadan ən uzaq xəzinəyə olan məsafəni göstərir!
Buna baxmayaraq, Luffy, bəlkə də hər şeyin itirilmədiyini ümid edərək, hər ada üçün xarab detektorunun göstərdiyi məsafələri saxladı. İndi o, hansı adalarda xəzinə tapma ehtimalının daha yüksək olduğunu düşünür.
Sizin vəzifəniz - Luffy-yə kömək etməkdir, n adanı ən yüksəkdən ən aşağı xəzinə ehtimalına görə sıralamaqdır, nəzərə alaraq ki, indi o, hər bir ada üçün detektorun göstərdiyi məsafələri bilir. Əvvəlcə hər adada müstəqil olaraq xəzinə olma ehtimalının 50% olduğunu qəbul edə bilərsiniz; başqa sözlə, xəzinə adalarının alt qüməsi ilə eyni ehtimala malik olan hər bir alt qümə ola bilər.
Giriş məlumatları
Birinci sətir adaların sayını n (1 ≤ n ≤ 250000) ehtiva edir. Növbəti n - 1 sətir körpüləri təsvir edir. Hər körpü iki fərqli adanı birləşdirir. Sonuncu sətir Luffy-nin detektorunda göstərilən hər ada üçün n tam ədədi - məsafələri (körpülərin sayı) ehtiva edir.
Zəmanət verilir ki, giriş məlumatları ilə uyğun gələn ən azı bir boş olmayan alt qümə mövcuddur.
Çıxış məlumatları
n ölçüsündə bir permütasiya verin - xəzinə tapma ehtimalının ən yüksəkdən ən aşağıya doğru sıralanmış adaların sırası. Əgər iki ada eyni ehtimalla xəzinə ehtiva edirsə, onları nömrələrinin artan sırasına görə verin.