Lille P fick ett träd med $n$ noder, rotat i nod $1$, och en permutation $p_i$ av längd $n$.

För varje nod $u$ i trädet kallas en nod $v$ i delträdet till $u$ viktig om och endast om $u \ne v$ och positionen för $v$ i permutationen kommer före positionen för $u$. Låt $d_u$ vara det minsta avståndet från $u$ till någon viktig nod (eller $d_u = -1$ om det inte finns några viktiga noder för $u$). Avståndet mellan två noder definieras som antalet kanter på den enkla vägen som förbinder dem.

Du får det rotade trädet och arrayen $d_i$. Din uppgift är att hitta en möjlig permutation $p_i$; om det finns flera giltiga permutationer, hitta den lexikografiskt minsta.

Kom ihåg att en permutation $a$ är lexikografiskt mindre än en permutation $b$ om och endast om det finns ett index $i$ ($1 \le i \le n$) sådant att $a_i < b_i$ och för alla $1 \le j < i$, $a_j = b_j$.

Indata

Den första raden innehåller ett heltal $T$ ($1 \le T \le 5 \times 10^4$), som representerar antalet testfall.

För varje testfall innehåller den första raden ett heltal $n$ ($2 \le n \le 5 \times 10^5$), som anger antalet noder i trädet.

Den andra raden innehåller $n$ heltal $d_1, d_2, \dots, d_n$ ($-1 \le d_i \le n$).

Var och en av de följande $n - 1$ raderna innehåller två heltal $u$ och $v$ ($1 \le u, v \le n, u \ne v$), som representerar en kant som förbinder noderna $u$ och $v$ i trädet.

Det garanteras att summan av $n$ över alla testfall inte överstiger $5 \times 10^5$.

Utdata

För varje testfall, skriv ut en enda rad som innehåller $n$ positiva heltal separerade med mellanslag, vilka representerar den lexikografiskt minsta giltiga permutationen; eller skriv ut $-1$ om ingen giltig permutation existerar.

Exempel

Indata

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

Notering

För det första testfallet är $p = [1, 2, 3, 4, 5]$ inte giltig eftersom nod $2$ inte har några viktiga noder, så $d_2 = -1 \ne 1$. På samma sätt är $p = [3, 4, 1, 5, 2]$ inte giltig eftersom $d_1 = 2 \ne -1$.