Красящие гейзеры

Однажды Люси нашла пещеру на одной из планет системы 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$ баллов): без дополнительных ограничений.