Il piccolo P ha ricevuto un albero con $n$ nodi, radicato nel nodo $1$, e una permutazione $p_i$ di lunghezza $n$.

Per ogni nodo $u$ nell'albero, un nodo $v$ nel sottoalbero di $u$ è chiamato importante se e solo se $u \ne v$ e la posizione di $v$ nella permutazione appare prima di quella di $u$. Sia $d_u$ la distanza minima da $u$ a qualsiasi nodo importante (oppure $d_u = -1$ se non ci sono nodi importanti per $u$). La distanza tra due nodi è definita come il numero di archi sul cammino semplice che li collega.

Ti vengono dati l'albero radicato e l'array $d_i$. Il tuo compito è trovare una possibile permutazione $p_i$; se esistono più permutazioni valide, trova quella lessicograficamente più piccola.

Ricorda che una permutazione $a$ è lessicograficamente più piccola di una permutazione $b$ se e solo se esiste un indice $i$ ($1 \le i \le n$) tale che $a_i < b_i$ e per tutti gli $1 \le j < i$, $a_j = b_j$.

Input

La prima riga contiene un intero $T$ ($1 \le T \le 5 \times 10^4$), che rappresenta il numero di casi di test.

Per ogni caso di test, la prima riga contiene un intero $n$ ($2 \le n \le 5 \times 10^5$), che indica il numero di nodi nell'albero.

La seconda riga contiene $n$ interi $d_1, d_2, \dots, d_n$ ($-1 \le d_i \le n$).

Ciascuna delle successive $n - 1$ righe contiene due interi $u$ e $v$ ($1 \le u, v \le n, u \ne v$), che rappresentano un arco che collega i nodi $u$ e $v$ nell'albero.

È garantito che la somma di $n$ su tutti i casi di test non supera $5 \times 10^5$.

Output

Per ogni caso di test, stampa una singola riga contenente $n$ interi positivi separati da spazi, che rappresentano la permutazione valida lessicograficamente più piccola; oppure stampa $-1$ se non esiste alcuna permutazione valida.

Esempio

Input

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

Output

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

Nota

Per il primo caso di test, $p = [1, 2, 3, 4, 5]$ non è valida perché il nodo $2$ non ha nodi importanti, quindi $d_2 = -1 \ne 1$. Allo stesso modo, $p = [3, 4, 1, 5, 2]$ non è valida perché $d_1 = 2 \ne -1$.