Маленький 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$.