Little P menerima sebuah pohon dengan $n$ simpul, yang berakar di simpul $1$, serta sebuah permutasi $p_i$ dengan panjang $n$.

Untuk setiap simpul $u$ di dalam pohon, sebuah simpul $v$ di dalam subpohon dari $u$ disebut penting jika dan hanya jika $u \ne v$ dan posisi $v$ di dalam permutasi muncul sebelum posisi $u$. Misalkan $d_u$ adalah jarak minimum dari $u$ ke simpul penting mana pun (atau $d_u = -1$ jika tidak ada simpul penting untuk $u$). Jarak antara dua simpul didefinisikan sebagai jumlah sisi pada lintasan sederhana yang menghubungkan keduanya.

Anda diberikan pohon berakar tersebut dan larik $d_i$. Tugas Anda adalah mencari permutasi $p_i$ yang mungkin; jika terdapat beberapa permutasi yang valid, carilah yang terkecil secara leksikografis.

Ingat bahwa permutasi $a$ lebih kecil secara leksikografis daripada permutasi $b$ jika dan hanya jika terdapat indeks $i$ ($1 \le i \le n$) sehingga $a_i < b_i$ dan untuk semua $1 \le j < i$, $a_j = b_j$.

Masukan

Baris pertama berisi sebuah bilangan bulat $T$ ($1 \le T \le 5 \times 10^4$), yang menyatakan jumlah kasus uji.

Untuk setiap kasus uji, baris pertama berisi sebuah bilangan bulat $n$ ($2 \le n \le 5 \times 10^5$), yang menyatakan jumlah simpul di dalam pohon.

Baris kedua berisi $n$ bilangan bulat $d_1, d_2, \dots, d_n$ ($-1 \le d_i \le n$).

Masing-masing dari $n - 1$ baris berikutnya berisi dua bilangan bulat $u$ dan $v$ ($1 \le u, v \le n, u \ne v$), yang menyatakan sebuah sisi yang menghubungkan simpul $u$ dan $v$ di dalam pohon.

Dijamin bahwa jumlah dari $n$ di seluruh kasus uji tidak melebihi $5 \times 10^5$.

Keluaran

Untuk setiap kasus uji, keluarkan satu baris yang berisi $n$ bilangan bulat positif yang dipisahkan oleh spasi, yang menyatakan permutasi valid terkecil secara leksikografis; atau keluarkan $-1$ jika tidak ada permutasi yang valid.

Contoh

Masukan

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

Keluaran

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

Catatan

Untuk kasus uji pertama, $p = [1, 2, 3, 4, 5]$ tidak valid karena simpul $2$ tidak memiliki simpul penting, sehingga $d_2 = -1 \ne 1$. Demikian pula, $p = [3, 4, 1, 5, 2]$ tidak valid karena $d_1 = 2 \ne -1$.