小 P 收到一棵有 $n$ 個節點、以節點 $1$ 為根嘅樹，同埋一個長度為 $n$ 嘅排列 $p_i$。

對於樹中嘅每個節點 $u$，$u$ 子樹入面嘅一個節點 $v$ 被稱為重要嘅，當且僅當 $u \ne v$ 且 $v$ 喺排列中出現嘅位置喺 $u$ 之前。設 $d_u$ 為 $u$ 到任何重要節點嘅最小距離（如果 $u$ 冇重要節點，則 $d_u = -1$）。兩個節點之間嘅距離定義為連接佢哋嘅簡單路徑上嘅邊數。

而家畀定呢棵有根樹同數組 $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$。