Little P ได้รับต้นไม้ที่มี $n$ โหนด โดยมีรากอยู่ที่โหนด $1$ และการเรียงสับเปลี่ยน $p_i$ ที่มีความยาว $n$

สำหรับแต่ละโหนด $u$ ในต้นไม้ โหนด $v$ ในต้นไม้ย่อยของ $u$ จะถูกเรียกว่า สำคัญ ก็ต่อเมื่อ $u \ne v$ และตำแหน่งของ $v$ ในการเรียงสับเปลี่ยนปรากฏก่อนตำแหน่งของ $u$ ให้ $d_u$ เป็นระยะทางที่สั้นที่สุดจาก $u$ ไปยังโหนดสำคัญใดๆ (หรือ $d_u = -1$ หากไม่มีโหนดสำคัญสำหรับ $u$) ระยะทางระหว่างสองโหนดนิยามเป็นจำนวนเส้นเชื่อมบนวิถีเชิงเดียวที่เชื่อมระหว่างโหนดทั้งสอง

คุณได้รับต้นไม้มีรากและอาร์เรย์ $d_i$ งานของคุณคือการหาการเรียงสับเปลี่ยน $p_i$ ที่เป็นไปได้ หากมีการเรียงสับเปลี่ยนที่ถูกต้องหลายแบบ ให้หาแบบที่มีลำดับพจนานุกรมน้อยที่สุด

ทบทวนว่าการเรียงสับเปลี่ยน $a$ มีลำดับพจนานุกรมน้อยกว่าการเรียงสับเปลี่ยน $b$ ก็ต่อเมื่อมีดัชนี $i$ ($1 \le i \le n$) ที่ทำให้ $a_i < b_i$ และสำหรับทุกๆ $1 \le j < i$ จะได้ $a_j = b_j$

ข้อมูลนำเข้า

บรรทัดแรกประกอบด้วยจำนวนเต็ม $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$ ($1 \le u, v \le n, u \ne v$) แทนเส้นเชื่อมที่เชื่อมโหนด $u$ และ $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$