Petit P a reçu un arbre à $n$ nœuds, enraciné au nœud $1$, ainsi qu'une permutation $p_i$ de longueur $n$.

Pour chaque nœud $u$ de l'arbre, un nœud $v$ dans le sous-arbre de $u$ est dit important si et seulement si $u \ne v$ et la position de $v$ dans la permutation apparaît avant celle de $u$. Soit $d_u$ la distance minimale entre $u$ et n'importe quel nœud important (ou $d_u = -1$ s'il n'y a aucun nœud important pour $u$). La distance entre deux nœuds est définie comme le nombre d'arêtes sur le chemin simple qui les relie.

On vous donne l'arbre enraciné et le tableau $d_i$. Votre tâche consiste à trouver une permutation possible $p_i$ ; s'il existe plusieurs permutations valides, trouvez la plus petite dans l'ordre lexicographique.

Rappelons qu'une permutation $a$ est lexicographiquement plus petite qu'une permutation $b$ si et seulement s'il existe un indice $i$ ($1 \le i \le n$) tel que $a_i < b_i$ et pour tout $1 \le j < i$, $a_j = b_j$.

Entrée

La première ligne contient un entier $T$ ($1 \le T \le 5 \times 10^4$), représentant le nombre de cas de test.

Pour chaque cas de test, la première ligne contient un entier $n$ ($2 \le n \le 5 \times 10^5$), indiquant le nombre de nœuds dans l'arbre.

La deuxième ligne contient $n$ entiers $d_1, d_2, \dots, d_n$ ($-1 \le d_i \le n$).

Chacune des $n - 1$ lignes suivantes contient deux entiers $u$ et $v$ ($1 \le u, v \le n, u \ne v$), représentant une arête reliant les nœuds $u$ et $v$ dans l'arbre.

Il est garanti que la somme de $n$ sur l'ensemble des cas de test ne dépasse pas $5 \times 10^5$.

Sortie

Pour chaque cas de test, affichez une seule ligne contenant $n$ entiers positifs séparés par des espaces, représentant la plus petite permutation valide dans l'ordre lexicographique ; ou affichez $-1$ s'il n'existe aucune permutation valide.

Exemple

Entrée

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

Sortie

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

Note

Pour le premier cas de test, $p = [1, 2, 3, 4, 5]$ n'est pas valide car le nœud $2$ n'a aucun nœud important, donc $d_2 = -1 \ne 1$. De même, $p = [3, 4, 1, 5, 2]$ n'est pas valide car $d_1 = 2 \ne -1$.