Little P received a tree with $n$ nodes, rooted at node $1$, and a permutation $p_i$ of length $n$.

For each node $u$ in the tree, a node $v$ in the subtree of $u$ is called important if and only if $u \ne v$ and the position of $v$ in the permutation appears before that of $u$. Let $d_u$ be the minimum distance from $u$ to any important node (or $d_u = -1$ if there are no important nodes for $u$). The distance between two nodes is defined as the number of edges on the simple path connecting them.

You are given the rooted tree and the array $d_i$. Your task is to find a possible permutation $p_i$; if multiple valid permutations exist, find the lexicographically smallest one.

Recall that a permutation $a$ is lexicographically smaller than a permutation $b$ if and only if there exists an index $i$ ($1 \le i \le n$) such that $a_i < b_i$ and for all $1 \le j < i$, $a_j = b_j$.

Input

The first line contains an integer $T$ ($1 \le T \le 5 \times 10^4$), representing the number of test cases.

For each test case, the first line contains an integer $n$ ($2 \le n \le 5 \times 10^5$), indicating the number of nodes in the tree.

The second line contains $n$ integers $d_1, d_2, \dots, d_n$ ($-1 \le d_i \le n$).

Each of the next $n - 1$ lines contains two integers $u$ and $v$ ($1 \le u, v \le n, u \ne v$), representing an edge connecting nodes $u$ and $v$ in the tree.

It is guaranteed that the sum of $n$ over all test cases does not exceed $5 \times 10^5$.

Output

For each test case, output a single line containing $n$ positive integers separated by spaces, representing the lexicographically smallest valid permutation; or output $-1$ if no valid permutation exists.

Example

Input

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

Output

1 3 2 4 5
-1
6 1 2 3 4 5 7 8 9 10

Note

For the first test case, $p = [1, 2, 3, 4, 5]$ is not valid because node $2$ has no important nodes, so $d_2 = -1 \ne 1$. Similarly, $p = [3, 4, 1, 5, 2]$ is not valid because $d_1 = 2 \ne -1$.