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$.