El pequeño P recibió un árbol con $n$ nodos, con raíz en el nodo $1$, y una permutación $p_i$ de longitud $n$.

Para cada nodo $u$ del árbol, un nodo $v$ en el subárbol de $u$ se llama importante si y solo si $u \ne v$ y la posición de $v$ en la permutación aparece antes que la de $u$. Sea $d_u$ la distancia mínima desde $u$ hasta cualquier nodo importante (o $d_u = -1$ si no hay nodos importantes para $u$). La distancia entre dos nodos se define como el número de aristas en el camino simple que los conecta.

Se te da el árbol con raíz y el arreglo $d_i$. Tu tarea es encontrar una permutación posible $p_i$; si existen múltiples permutaciones válidas, encuentra la lexicográficamente menor.

Recuerda que una permutación $a$ es lexicográficamente menor que una permutación $b$ si y solo si existe un índice $i$ ($1 \le i \le n$) tal que $a_i < b_i$ y para todo $1 \le j < i$, $a_j = b_j$.

Entrada

La primera línea contiene un entero $T$ ($1 \le T \le 5 \times 10^4$), que representa el número de casos de prueba.

Para cada caso de prueba, la primera línea contiene un entero $n$ ($2 \le n \le 5 \times 10^5$), que indica el número de nodos en el árbol.

La segunda línea contiene $n$ enteros $d_1, d_2, \dots, d_n$ ($-1 \le d_i \le n$).

Cada una de las siguientes $n - 1$ líneas contiene dos enteros $u$ y $v$ ($1 \le u, v \le n, u \ne v$), que representan una arista que conecta los nodos $u$ y $v$ en el árbol.

Se garantiza que la suma de $n$ en todos los casos de prueba no supera $5 \times 10^5$.

Salida

Para cada caso de prueba, imprime una sola línea con $n$ enteros positivos separados por espacios, que representen la permutación válida lexicográficamente menor; o imprime $-1$ si no existe ninguna permutación válida.

Ejemplo

Entrada

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

Salida

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

Nota

Para el primer caso de prueba, $p = [1, 2, 3, 4, 5]$ no es válida porque el nodo $2$ no tiene nodos importantes, por lo que $d_2 = -1 \ne 1$. Del mismo modo, $p = [3, 4, 1, 5, 2]$ no es válida porque $d_1 = 2 \ne -1$.