Malujące gejzery#11731
Pewnego dnia Lucy znalazła jaskinię na jednej z planet systemu Link-Cut. Jaskinia składa się z sal i n - 1 przejść, z których każde łączy dwie sale, a z każdej sali można dotrzeć do każdej innej za pomocą przejść.
W każdej sali znajduje się malujący gejzer. Kiedy malujący gejzer w sali o numerze wybucha, maluje na kolor numer wszystkie sale, których odległość od sali nie przekracza d_i. Odległość między dwiema salami określa się jako minimalna liczba przejść, które należy pokonać, aby się między nimi przemieścić.
Lucy zna strukturę jaskini, kolory niektórych sal, a także to, że każdy gejzer wybuchł dokładnie jeden raz. Na podstawie tych informacji określ dowolną możliwą kolejność, w jakiej mogły odbywać się wybuchy.
Pierwszy wiersz zawiera jedną liczbę całkowitą (2 \le n \le 10^5) — liczbę sal w jaskini.
Drugi wiersz zawiera liczb całkowitych d_1, d_2, ... , d_n (0 \le d_i \le n - 1) — parametry odległości malowania dla gejzerów.
Trzeci wiersz zawiera liczb całkowitych c_1, c_2, ... , c_n (-1 \le c_i \le n), gdzie c_i to albo numer koloru -ej sali, albo , jeśli kolor -ej sali nie jest znany.
Następne n - 1 wierszy opisują przejścia. -szy wiersz zawiera dwie liczby całkowite u_i, v_i (1 \le u_i, v_i \le n, u_i \ne v_i) — sale połączone przejściem.
W jedynym wierszu wypisz liczb całkowitych p_1, p_2, ... , p_n, gdzie p_i to numer sali, w której gejzer wybuchł -szy. Gwarantuje się, że istnieje przynajmniej jedna kolejność odpowiadająca danym wejściowym.
Przykład
Przykład 1
W pierwszym przykładzie kolory po wybuchach, pod warunkiem, że miały miejsce w kolejności opisanej w wyjściu, będą następujące:
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
( punktów): n \le 8;
( punktów): d_i = 1 (1 \le i \le n);
( punktów): u_i = 1 (1 \le i \le n - 1);
( punktów): n \le 5 \cdot 10^4;
( punktów): bez dodatkowych ograniczeń.