一天，小 P 收到了一棵有 $n$ 个节点的树，根节点为 1，以及一个长度为 $n$ 的排列 $p_i$。小 P 想起了一个问题：

给定一棵有根树和一个排列。对于树中的每个节点 $u$，当且仅当 $u \neq v$ 且 $v$ 在排列中的位置在 $u$ 之前时，$u$ 的子树中的节点 $v$ 被称为重要节点。设 $d_u$ 为 $u$ 到任意重要节点的最小距离。特别地，如果 $u$ 没有重要节点，则令 $d_u = -1$。树中两点之间的距离定义为它们之间简单路径上的边数。

在竭尽全力计算出每个节点 $i$ 的 $d_i$ 后，小 P 把数据搁置在了一旁。随着时间的流逝，小 P 重新审视了这个问题，此时有根树的结构和 $d_i$ 数组还在，但排列 $p_i$ 已经丢失了。现在，小 P 希望你能根据现有信息提供一个可能的排列 $p_i$。如果存在多个可能的排列 $p_i$，你需要找到字典序最小的一个。

对于两个长度为 $n$ 的排列 $a$ 和 $b$，我们称 $a$ 的字典序小于 $b$，当且仅当存在 $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 \neq v$)，表示连接节点 $u$ 和节点 $v$ 的一条边。保证这 $n - 1$ 条边构成一棵树。

保证所有测试数据的 $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

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 \neq 1$。类似地，排列 $p = [3, 4, 1, 5, 2]$ 也是不可行的，因为在此排列下，$d_1 = 2 \neq -1$。