Pikku P sai puun, jossa on $n$ solmua ja jonka juuri on solmu $1$, sekä pituuden $n$ permutaation $p_i$.

Jokaiselle puun solmulle $u$ solmun $u$ alipuussa olevaa solmua $v$ kutsutaan tärkeäksi jos ja vain jos $u \ne v$ ja solmun $v$ sijainti permutaatiossa esiintyy ennen solmun $u$ sijaintia. Olkoon $d_u$ pienin etäisyys solmusta $u$ mihin tahansa tärkeään solmuun (tai $d_u = -1$, jos solmulle $u$ ei ole tärkeitä solmuja). Kahden solmun välinen etäisyys määritellään niitä yhdistävän yksinkertaisen polun kaarien lukumääränä.

Sinulle annetaan juurellinen puu ja taulukko $d_i$. Tehtäväsi on löytää mahdollinen permutaatio $p_i$; jos kelvollisia permutaatioita on useita, etsi niistä leksikografisesti pienin.

Muista, että permutaatio $a$ on leksikografisesti pienempi kuin permutaatio $b$ jos ja vain jos on olemassa indeksi $i$ ($1 \le i \le n$) siten, että $a_i < b_i$ ja kaikilla $1 \le j < i$ pätee $a_j = b_j$.

Syöte

Ensimmäinen rivi sisältää kokonaisluvun $T$ ($1 \le T \le 5 \times 10^4$), joka kuvaa testitapausten lukumäärää.

Jokaisessa testitapauksessa ensimmäinen rivi sisältää kokonaisluvun $n$ ($2 \le n \le 5 \times 10^5$), joka ilmaisee puun solmujen lukumäärän.

Toinen rivi sisältää $n$ kokonaislukua $d_1, d_2, \dots, d_n$ ($-1 \le d_i \le n$).

Jokainen seuraavista $n - 1$ rivistä sisältää kaksi kokonaislukua $u$ ja $v$ ($1 \le u, v \le n, u \ne v$), jotka kuvaavat solmut $u$ ja $v$ yhdistävää kaarta puussa.

On taattu, että lukujen $n$ summa kaikkien testitapausten yli ei ylitä arvoa $5 \times 10^5$.

Tuloste

Tulosta jokaista testitapausta kohden yksi rivi, joka sisältää $n$ positiivista kokonaislukua välilyönnein erotettuina, kuvaten leksikografisesti pienintä kelvollista permutaatiota; tai tulosta $-1$, jos kelvollista permutaatiota ei ole olemassa.

Esimerkki

Syöte

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

Tuloste

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

Huomautus

Ensimmäisessä testitapauksessa $p = [1, 2, 3, 4, 5]$ ei ole kelvollinen, koska solmulla $2$ ei ole tärkeitä solmuja, joten $d_2 = -1 \ne 1$. Samoin $p = [3, 4, 1, 5, 2]$ ei ole kelvollinen, koska $d_1 = 2 \ne -1$.