Geyzerləri Rəngləmə#11731
Bir dəfə, Lusi Link-Cut sistemindəki planetlərdən birində bir mağara tapdı. Mağara zalından və n - 1 keçidindən ibarətdir; hər bir keçid iki zalı birləşdirir və keçidlər vasitəsilə istənilən digər zala çatmaq mümkündür.
Hər bir zalda bir rəngləmə geyzeri var. Zalda geyzeri partlayanda, zalından d_i məsafədə olan bütün zallar nömrəli rəngə boyanır. İki zal arasındakı məsafə, onlardan birindən digərinə keçmək üçün keçməli olduğunuz keçidlərin minimum sayısı ilə müəyyən edilir.
Lusi mağaranın strukturunu, bəzi zalların rənglərini bilir və hər geyzerin dəqiq bir dəfə partladığını bilir. Bu məlumatlara əsaslanaraq, partlayışların baş verə biləcəyi mümkün bir sıralamanı müəyyən edin.
Birinci sətirdə bir tam ədəd (2 \le n \le 10^5) — mağaradakı zalların sayı.
İkinci sətirdə tam ədəd d_1, d_2, ... , d_n (0 \le d_i \le n - 1) — geyzerlərin rəngləmə məsafəsi parametrləri.
Üçüncü sətirdə tam ədəd c_1, c_2, ... , c_n (-1 \le c_i \le n), burada c_i ya -ci zalın rəng nömrəsidir, ya da -dir, əgər -ci zalın rəngi məlum deyilsə.
Sonra gələn n - 1 sətir keçidləri təsvir edir. -ci sətir iki tam ədəd u_i, v_i (1 \le u_i, v_i \le n, u_i \ne v_i) — keçid vasitəsilə birləşdirilən zallar.
Bir sətirdə tam ədəd p_1, p_2, ... , p_n çap edin, burada p_i -ci partlayışın baş verdiyi zalın nömrəsidir. Giriş məlumatlarına uyğun ən azı bir sıralamanın mövcud olduğu təmin edilir.
Nümunə
Nümunə 1
Birinci nümunədə, burada hər partlayışdan sonra zalların rəngləri var, onların çıxışda verilən sıraya uyğun baş verdiyini düşünərək:
1, 1, 1, 1, 1
5, 1, 1, 1, 5
4, 1, 1, 4, 5
3, 1, 3, 4, 5
2, 2, 3, 4, 5
( bal): n \le 8;
( bal): d_i = 1 (1 \le i \le n);
( bal): u_i = 1 (1 \le i \le n - 1);
( bal): n \le 5 \cdot 10^4;
( bal): əlavə məhdudiyyət yoxdur.