Маленький P получил дерево из $n$ вершин с корнем в вершине $1$ и перестановку $p_i$ длины $n$.

Для каждой вершины $u$ дерева вершина $v$ в поддереве $u$ называется важной тогда и только тогда, когда $u \ne v$ и позиция $v$ в перестановке находится раньше позиции $u$. Пусть $d_u$ — минимальное расстояние от $u$ до какой-либо важной вершины (или $d_u = -1$, если для $u$ нет важных вершин). Расстояние между двумя вершинами определяется как количество рёбер на простом пути, соединяющем их.

Вам даны корневое дерево и массив $d_i$. Ваша задача — найти возможную перестановку $p_i$; если подходящих перестановок несколько, найдите лексикографически наименьшую.

Напомним, что перестановка $a$ лексикографически меньше перестановки $b$ тогда и только тогда, когда существует индекс $i$ ($1 \le i \le n$) такой, что $a_i < b_i$, а для всех $1 \le j < i$ выполняется $a_j = b_j$.

Входные данные

Первая строка содержит целое число $T$ ($1 \le T \le 5 \times 10^4$) — количество наборов входных данных.

Для каждого набора входных данных первая строка содержит целое число $n$ ($2 \le n \le 5 \times 10^5$) — количество вершин в дереве.

Вторая строка содержит $n$ целых чисел $d_1, d_2, \dots, d_n$ ($-1 \le d_i \le n$).

Каждая из следующих $n - 1$ строк содержит два целых числа $u$ и $v$ ($1 \le u, v \le n, u \ne v$), обозначающих ребро, соединяющее вершины $u$ и $v$ в дереве.

Гарантируется, что сумма $n$ по всем наборам входных данных не превышает $5 \times 10^5$.

Выходные данные

Для каждого набора входных данных выведите одну строку, содержащую $n$ положительных целых чисел через пробел — лексикографически наименьшую подходящую перестановку, или выведите $-1$, если подходящей перестановки не существует.

Пример

Входные данные

3
5
-1 1 -1 -1 -1
1 2
2 3
2 4
1 5
10
0 1 1 1 -1 -1 -1 -1 -1 -1
5 3
4 3
8 4
4 2
4 1
2 10
9 5
5 7
6 1
10
2 -1 -1 -1 1 -1 -1 -1 -1 1
2 6
6 10
5 6
5 7
8 10
3 6
5 4
6 9
1 10

Выходные данные

1 3 2 4 5
-1
6 1 2 3 4 5 7 8 9 10

Примечание

В первом наборе входных данных перестановка $p = [1, 2, 3, 4, 5]$ не подходит, так как у вершины $2$ нет важных вершин, поэтому $d_2 = -1 \ne 1$. Аналогично, $p = [3, 4, 1, 5, 2]$ не подходит, так как $d_1 = 2 \ne -1$.