تلقى الصغير 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$.