Кішкентай P төбесі $1$-ші төбеде орналасқан $n$ төбесі бар ағашты және ұзындығы $n$ болатын $p_i$ орын алмастыруын алды.

Ағаштағы әрбір $u$ төбесі үшін, $u$ ішкі ағашындағы $v$ төбесі $u \ne v$ болса және $v$-ның орын алмастырудағы орны $u$-дан бұрын келсе және тек сонда ғана маңызды деп аталады. $d_u$ — $u$ төбесінен кез келген маңызды төбеге дейінгі ең قысқа қашықтық болсын (немесе $u$ үшін маңызды төбелер болмаса, $d_u = -1$). Екі төбе арасындағы қашықтық оларды қосатын қарапайым жолдағы қырлар саны ретінде анықталады.

Сізге түбірлі ағаш пен $d_i$ массиві берілген. Сіздің міндетіңіз — мүмкін болатын $p_i$ орын алмастыруын табу; егер бірнеше жарамды орын алмастыру болса, лексикографиялық жағынан ең кішісін табыңыз.

Еске салсақ, $a$ орын алмастыруы $b$ орын алмастыруынан лексикографиялық жағынан кіші болады сонда және тек сонда ғана, егер $a_i < b_i$ және барлық $1 \le j < i$ үшін $a_j = b_j$ болатындай $i$ ($1 \le i \le n$) индексі табылса.

Кіріс деректер

Бірінші жолда тесттер санын білдіретін $T$ ($1 \le T \le 5 \times 10^4$) бүтін саны берілген.

Әрбір тест үшін бірінші жолда ағаштағы төбелер санын білдіретін $n$ ($2 \le n \le 5 \times 10^5$) бүтін саны берілген.

Екінші жолда $n$ бүтін сан $d_1, d_2, \dots, d_n$ ($-1 \le d_i \le n$) берілген.

Келесі $n - 1$ жолдың әрқайсысында ағаштағы $u$ мен $v$ төбелерін қосатын қырды білдіретін екі бүтін сан $u$ және $v$ ($1 \le u, v \le n, u \ne v$) берілген.

Барлық тесттер бойынша $n$ қосындысы $5 \times 10^5$ мәнінен аспайтынына кепілдік беріледі.

Шығыс деректер

Әрбір тест үшін лексикографиялық жағынан ең кіші жарамды орын алмастыруды білдіретін, бос орындармен бөлінген $n$ оң бүтін саннан тұратын бір жолды шығарыңыз; немесе жарамды орын алмастыру болмаса, $-1$ шығарыңыз.

Мысал

Кіріс деректер

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

Шығыс деректер

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

Ескертпе

Бірінші тест үшін $p = [1, 2, 3, 4, 5]$ жарамсыз, себебі $2$-ші төбенің маңызды төбелері жоқ, сондықтан $d_2 = -1 \ne 1$. Сол сияқты, $p = [3, 4, 1, 5, 2]$ де жарамсыз, себебі $d_1 = 2 \ne -1$.