Der kleine P hat einen Baum mit $n$ Knoten, der am Knoten $1$ gewurzelt ist, und eine Permutation $p_i$ der Länge $n$ erhalten.

Für jeden Knoten $u$ im Baum wird ein Knoten $v$ im Teilbaum von $u$ genau dann als wichtig bezeichnet, wenn $u \ne v$ gilt und die Position von $v$ in der Permutation vor der von $u$ liegt. Sei $d_u$ der minimale Abstand von $u$ zu einem beliebigen wichtigen Knoten (oder $d_u = -1$, falls es für $u$ keine wichtigen Knoten gibt). Der Abstand zwischen zwei Knoten ist definiert als die Anzahl der Kanten auf dem einfachen Pfad, der sie verbindet.

Gegeben sind der gewurzelte Baum und das Array $d_i$. Ihre Aufgabe ist es, eine mögliche Permutation $p_i$ zu finden; falls mehrere gültige Permutationen existieren, finden Sie die lexikografisch kleinste.

Zur Erinnerung: Eine Permutation $a$ ist genau dann lexikografisch kleiner als eine Permutation $b$, wenn es einen Index $i$ ($1 \le i \le n$) gibt, sodass $a_i < b_i$ und für alle $1 \le j < i$ die Gleichung $a_j = b_j$ gilt.

Eingabe

Die erste Zeile enthält eine ganze Zahl $T$ ($1 \le T \le 5 \times 10^4$), die Anzahl der Testfälle.

Für jeden Testfall enthält die erste Zeile eine ganze Zahl $n$ ($2 \le n \le 5 \times 10^5$), die Anzahl der Knoten im Baum.

Die zweite Zeile enthält $n$ ganze Zahlen $d_1, d_2, \dots, d_n$ ($-1 \le d_i \le n$).

Jede der nächsten $n - 1$ Zeilen enthält zwei ganze Zahlen $u$ und $v$ ($1 \le u, v \le n, u \ne v$), die eine Kante zwischen den Knoten $u$ und $v$ im Baum darstellen.

Es wird garantiert, dass die Summe von $n$ über alle Testfälle hinweg $5 \times 10^5$ nicht überschreitet.

Ausgabe

Geben Sie für jeden Testfall eine einzige Zeile mit $n$ durch Leerzeichen getrennten positiven ganzen Zahlen aus, die die lexikografisch kleinste gültige Permutation darstellen; oder geben Sie $-1$ aus, falls keine gültige Permutation existiert.

Beispiel

Eingabe

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

Ausgabe

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

Hinweis

Für den ersten Testfall ist $p = [1, 2, 3, 4, 5]$ ungültig, da Knoten $2$ keine wichtigen Knoten hat und somit $d_2 = -1 \ne 1$ gilt. Ebenso ist $p = [3, 4, 1, 5, 2]$ ungültig, da $d_1 = 2 \ne -1$ gilt.