小 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$。