Geyzerləri Rəngləmə

Bir dəfə, Lusi Link-Cut sistemindəki planetlərdən birində bir mağara tapdı. Mağara $n$ 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 $i$ geyzeri partlayanda, $i$ zalından $d_i$ məsafədə olan bütün zallar $i$ 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.

Giriş verilənləri

Birinci sətirdə bir tam ədəd $n$ $(2\le n\le 10^5)$ — mağaradakı zalların sayı.

İkinci sətirdə $n$ 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ə $n$ tam ədəd $c_1,c_2,...,c_n$ $(-1\le c_i\le n)$, burada $c_i$ ya $i$-ci zalın rəng nömrəsidir, ya da $-1$-dir, əgər $i$-ci zalın rəngi məlum deyilsə.

Sonra gələn $n-1$ sətir keçidləri təsvir edir. $i$-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.

Çıxış verilənləri

Bir sətirdə $n$ tam ədəd $p_1,p_2,...,p_n$ çap edin, burada $p_i$ $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ələr

Qeyd

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$

Qiymətləndirmə

1. ($10$ bal): $n\le 8$;

2. ($40$ bal): $d_i=1(1\le i\le n)$;

3. ($30$ bal): $u_i=1(1\le i\le n-1)$;

4. ($80$ bal): $n\le 5\cdot 10^4$;

5. ($65$ bal): əlavə məhdudiyyət yoxdur.