Litli P fékk tré með $n$ hnútum, með rót í hnúti $1$, og umröðun $p_i$ af lengd $n$.

Fyrir hvern hnút $u$ í trénu kallast hnútur $v$ í hluttré $u$ mikilvægur ef og aðeins ef $u \ne v$ og staðsetning $v$ í umröðuninni kemur á undan staðsetningu $u$. Látum $d_u$ vera minnstu fjarlægð frá $u$ til nokkurs mikilvægs hnúts (eða $d_u = -1$ ef engir mikilvægir hnútar eru til fyrir $u$). Fjarlægðin milli tveggja hnúta er skilgreind sem fjöldi leggja á einfalda veginum sem tengir þá.

Þér er gefið rótaða tréð og fylkið $d_i$. Verkefni þitt er að finna mögulega umröðun $p_i$; ef margar gildar umraðanir eru til skal finna þá sem er minnst í stafrófsröð (lexicographically smallest).

Mundu að umröðun $a$ er minni í stafrófsröð en umröðun $b$ ef og aðeins ef til er vísi $i$ ($1 \le i \le n$) þannig að $a_i < b_i$ og fyrir öll $1 \le j < i$ gildir $a_j = b_j$.

Inntak

Fyrsta línan inniheldur heiltölu $T$ ($1 \le T \le 5 \times 10^4$), sem táknar fjölda prófunartilvika.

Fyrir hvert prófunartilvik inniheldur fyrsta línan heiltölu $n$ ($2 \le n \le 5 \times 10^5$), sem gefur til kynna fjölda hnúta í trénu.

Önnur línan inniheldur $n$ heiltölur $d_1, d_2, \dots, d_n$ ($-1 \le d_i \le n$).

Hver af næstu $n - 1$ línum inniheldur tvær heiltölur $u$ og $v$ ($1 \le u, v \le n, u \ne v$), sem tákna legg sem tengir hnúta $u$ og $v$ í trénu.

Tryggt er að summa $n$ yfir öll prófunartilvik fari ekki yfir $5 \times 10^5$.

Úttak

Fyrir hvert prófunartilvik skal prenta eina línu sem inniheldur $n$ jákvæðar heiltölur aðskildar með bilum, sem tákna þá gildu umröðun sem er minnst í stafrófsröð; eða prenta $-1$ ef engin gild umröðun er til.

Dæmi

Inntak

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

Úttak

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

Athugasemd

Fyrir fyrsta prófunartilvikið er $p = [1, 2, 3, 4, 5]$ ekki gild vegna þess að hnútur $2$ hefur enga mikilvæga hnúta, þannig að $d_2 = -1 \ne 1$. Sömuleiðis er $p = [3, 4, 1, 5, 2]$ ekki gild vegna þess að $d_1 = 2 \ne -1$.