Кольорові гейзери

Одного разу Люся знайшла печеру на одній з планет системи Link-Cut. Печера складається з $n$ залів і $n-1$ проходів, кожен прохід з'єднує два зали, і з кожного залу можна дістатися по проходах до будь-якого іншого.

У кожному залі розташований кольоровий гейзер. Коли кольоровий гейзер у залі з номером $i$ вивергається, він фарбує в колір з номером $i$ всі зали, відстань до яких від залу $i$ не більше, ніж $d_i$. Відстань між двома залами визначається як мінімальна кількість переходів, які потрібно пройти, щоб переміститися між ними.

Люсі відома структура печери, кольори деяких залів, а також те, що кожен гейзер вивергався рівно один раз. За даною інформацією визначте будь-який з можливих порядків, у якому могли відбуватися виверження.

Вхідні дані

Перша строка містить єдине ціле число $n$ $(2\le n\le 10^5)$ — кількість залів у печері.

Друга строка містить $n$ цілих чисел $d_1,d_2,...,d_n$ $(0\le d_i\le n-1)$ — параметри відстаней фарбування для гейзерів.

Третя строка містить $n$ цілих чисел $c_1,c_2,...,c_n$ $(-1\le c_i\le n)$, де $c_i$ це або номер кольору $i$-го залу, або $-1$, якщо колір $i$-го залу невідомий.

Наступні $n-1$ строк описують проходи. $i$-я строка містить два цілі числа $u_i,v_i$ $(1\le u_i,v_i\le n,u_i\ne v_i)$ — зали, з'єднані проходом.

Вихідні дані

В єдиній строкі виведіть $n$ цілих чисел $p_1,p_2,...,p_n$, де $p_i$ — номер залу, гейзер у якому вивергався $i$-м. Гарантується, що існує принаймні один порядок, що відповідає вхідним даним.

Приклади

Примітка

У першому прикладі кольори після вивержень, за умови що вони відбувалися в порядку, описаному в виводі, будуть наступними:

• $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$

Оцінювання

1. ($10$ балів): $n\le 8$;

2. ($40$ балів): $d_i=1(1\le i\le n)$;

3. ($30$ балів): $u_i=1(1\le i\le n-1)$;

4. ($80$ балів): $n\le 5\cdot 10^4$;

5. ($65$ балів): без додаткових обмежень.