Little P는 $1$번 정점이 루트인 $n$개의 정점으로 이루어진 트리와 길이 $n$인 순열 $p_i$를 받았습니다.

트리의 각 정점 $u$에 대해, $u$의 서브트리에 속한 정점 $v$는 $u \ne v$이고 순열에서 $v$의 위치가 $u$보다 앞에 나타날 때 그리고 그때에만 중요한 정점이라고 부릅니다. $d_u$를 $u$에서 임의의 중요한 정점까지의 최소 거리라고 합시다 (만약 $u$에 대한 중요한 정점이 없다면 $d_u = -1$입니다). 두 정점 사이의 거리는 두 정점을 잇는 단순 경로 위의 간선 개수로 정의됩니다.

루트 있는 트리와 배열 $d_i$가 주어집니다. 가능한 순열 $p_i$를 구하세요. 만약 조건을 만족하는 순열이 여러 개라면 사전순으로 가장 작은 것을 구하세요.

순열 $a$가 순열 $b$보다 사전순으로 작다는 것은 $a_i < b_i$이고 모든 $1 \le j < i$에 대해 $a_j = b_j$를 만족하는 인덱스 $i$ ($1 \le i \le n$)가 존재함을 의미합니다.

입력

첫 번째 줄에 테스트 케이스의 개수를 나타내는 정수 $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$를 연결하는 간선을 나타내는 두 정수 $u$와 $v$ ($1 \le u, v \le n, u \ne 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$이므로 올바르지 않습니다.