Lille P fikk et tre med $n$ noder, med rot i node $1$, og en permutasjon $p_i$ med lengde $n$.

For hver node $u$ i treet kalles en node $v$ i undertreet til $u$ viktig hvis og bare hvis $u \ne v$ og posisjonen til $v$ i permutasjonen kommer før posisjonen til $u$. La $d_u$ være den minste avstanden fra $u$ til en hvilken som helst viktig node (eller $d_u = -1$ hvis det ikke finnes noen viktige noder for $u$). Avstanden mellom to noder er definert som antallet kanter på den enkle stien som forbinder dem.

Du får oppgitt det rotfestede treet og tabellen $d_i$. Oppgaven din er å finne en mulig permutasjon $p_i$; hvis det finnes flere gyldige permutasjoner, skal du finne den leksikografisk minste.

Husk at en permutasjon $a$ er leksikografisk mindre enn en permutasjon $b$ hvis og bare hvis det finnes en indeks $i$ ($1 \le i \le n$) slik at $a_i < b_i$ og for alle $1 \le j < i$, $a_j = b_j$.

Inndata

Den første linjen inneholder et heltall $T$ ($1 \le T \le 5 \times 10^4$), som representerer antallet testtilfeller.

For hvert testtilfelle inneholder den første linjen et heltall $n$ ($2 \le n \le 5 \times 10^5$), som angir antallet noder i treet.

Den andre linjen inneholder $n$ heltall $d_1, d_2, \dots, d_n$ ($-1 \le d_i \le n$).

Hver av de neste $n - 1$ linjene inneholder to heltall $u$ og $v$ ($1 \le u, v \le n, u \ne v$), som representerer en kant som forbinder nodene $u$ og $v$ i treet.

Det garanteres at summen av $n$ over alle testtilfeller ikke overstiger $5 \times 10^5$.

Utdata

For hvert testtilfelle skal du skrive ut én enkelt linje som inneholder $n$ positive heltall adskilt med mellomrom, som representerer den leksikografisk minste gyldige permutasjonen; eller skrive ut $-1$ hvis ingen gyldig permutasjon finnes.

Eksempel

Inndata

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

Utdata

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

Forklaring

For det første testtilfellet er $p = [1, 2, 3, 4, 5]$ ikke gyldig fordi node $2$ ikke har noen viktige noder, så $d_2 = -1 \ne 1$. Tilsvarende er $p = [3, 4, 1, 5, 2]$ ikke gyldig fordi $d_1 = 2 \ne -1$.