Little P は頂点 $1$ を根とする $n$ 頂点の木と、長さ $n$ の順列 $p_i$ を受け取りました。

木の各頂点 $u$ について、$u$ の部分木に含まれる頂点 $v$ が重要であるとは、$u \ne v$ であり、かつ順列における $v$ の出現位置が $u$ の出現位置より前であることをいいます。$d_u$ を $u$ から任意の重要な頂点までの最小距離とします（ただし、$u$ に対する重要な頂点が存在しない場合は $d_u = -1$ とします）。2 つの頂点間の距離は、それらを結ぶ単純パス上の辺の本数として定義されます。

根付き木と配列 $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$) が与えられます。

2 行目には $n$ 個の整数 $d_1, d_2, \dots, d_n$ ($-1 \le d_i \le n$) が与えられます。

続く $n - 1$ 行には、それぞれ木の頂点 $u$ と $v$ を結ぶ辺を表す 2 つの整数 $u$ と $v$ ($1 \le u, v \le n, u \ne v$) が与えられます。

すべてのテストケースにおける $n$ の総和は $5 \times 10^5$ を超えないことが保証されます。

出力

各テストケースについて、辞書順で最小の条件を満たす順列を表す $n$ 個の正の整数を空白区切りで 1 行に出力してください。条件を満たす順列が存在しない場合は $-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

ノート

最初のテストケースでは、頂点 $2$ に重要な頂点が存在せず $d_2 = -1 \ne 1$ となるため、$p = [1, 2, 3, 4, 5]$ は条件を満たしません。同様に、$d_1 = 2 \ne -1$ となるため、$p = [3, 4, 1, 5, 2]$ も条件を満たしません。