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

Вхідні дані

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

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

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

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

Вихідні дані

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

Приклади

Приклад

Loading

Приклад 1

Loading

Примітка

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

$1, 1, 1, 1, 1$ 1, 1, 1, 1, 1
$5, 1, 1, 1, 5$ 5, 1, 1, 1, 5
$4, 1, 1, 4, 5$ 4, 1, 1, 4, 5
$3, 1, 3, 4, 5$ 3, 1, 3, 4, 5
$2, 2, 3, 4, 5$ 2, 2, 3, 4, 5

Оцінювання

( $10$ балів): $n \leq 8$ n \le 8;
( $40$ балів): $d_{i} = 1 (1 \leq i \leq n)$ d_i = 1 (1 \le i \le n);
( $30$ балів): $u_{i} = 1 (1 \leq i \leq n - 1)$ u_i = 1 (1 \le i \le n - 1);
( $80$ балів): $n \leq 5 \cdot 1 0^{4}$ n \le 5 \cdot 10^4;
( $65$ балів): без додаткових обмежень.