Little P nhận được một cây gồm $n$ đỉnh, có gốc tại đỉnh $1$, và một hoán vị $p_i$ có độ dài $n$.

Với mỗi đỉnh $u$ trong cây, một đỉnh $v$ trong cây con gốc $u$ được gọi là quan trọng khi và chỉ khi $u \ne v$ và vị trí của $v$ trong hoán vị xuất hiện trước vị trí của $u$. Gọi $d_u$ là khoảng cách nhỏ nhất từ $u$ đến bất kỳ đỉnh quan trọng nào (hoặc $d_u = -1$ nếu không có đỉnh quan trọng nào đối với $u$). Khoảng cách giữa hai đỉnh được định nghĩa là số cạnh trên đường đi đơn nối chúng.

Bạn được cho cây có gốc và mảng $d_i$. Nhiệm vụ của bạn là tìm một hoán vị $p_i$ khả dĩ; nếu có nhiều hoán vị hợp lệ, hãy tìm hoán vị có thứ tự từ điển nhỏ nhất.

Nhắc lại rằng hoán vị $a$ có thứ tự từ điển nhỏ hơn hoán vị $b$ khi và chỉ khi tồn tại một chỉ số $i$ ($1 \le i \le n$) sao cho $a_i < b_i$ và với mọi $1 \le j < i$, $a_j = b_j$.

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên $T$ ($1 \le T \le 5 \times 10^4$), biểu thị số lượng bộ dữ liệu.

Với mỗi bộ dữ liệu, dòng đầu tiên chứa một số nguyên $n$ ($2 \le n \le 5 \times 10^5$), cho biết số lượng đỉnh trong cây.

Dòng thứ hai chứa $n$ số nguyên $d_1, d_2, \dots, d_n$ ($-1 \le d_i \le n$).

Mỗi dòng trong $n - 1$ dòng tiếp theo chứa hai số nguyên $u$ và $v$ ($1 \le u, v \le n, u \ne v$), biểu thị một cạnh nối hai đỉnh $u$ và $v$ trong cây.

Dữ liệu đảm bảo tổng của $n$ trong tất cả các bộ dữ liệu không vượt quá $5 \times 10^5$.

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra một dòng gồm $n$ số nguyên dương cách nhau bởi dấu cách, biểu thị hoán vị hợp lệ có thứ tự từ điển nhỏ nhất; hoặc in ra $-1$ nếu không tồn tại hoán vị hợp lệ nào.

Ví dụ

Dữ liệu vào

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

Dữ liệu ra

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

Ghi chú

Đối với bộ dữ liệu đầu tiên, $p = [1, 2, 3, 4, 5]$ không hợp lệ vì đỉnh $2$ không có đỉnh quan trọng nào, nên $d_2 = -1 \ne 1$. Tương tự, $p = [3, 4, 1, 5, 2]$ không hợp lệ vì $d_1 = 2 \ne -1$.