Mały P otrzymał drzewo o $n$ wierzchołkach, ukorzenione w wierzchołku $1$, oraz permutację $p_i$ o długości $n$.

Dla każdego wierzchołka $u$ w drzewie, wierzchołek $v$ w poddrzewie $u$ nazywamy ważnym wtedy i tylko wtedy, gdy $u \ne v$ oraz pozycja $v$ w permutacji występuje przed pozycją $u$. Niech $d_u$ oznacza minimalną odległość od $u$ do dowolnego ważnego wierzchołka (lub $d_u = -1$, jeśli dla $u$ nie ma ważnych wierzchołków). Odległość między dwoma wierzchołkami definiujemy jako liczbę krawędzi na ścieżce prostej łączącej te wierzchołki.

Dane jest drzewo ukorzenione oraz tablica $d_i$. Twoim zadaniem jest znalezienie możliwej permutacji $p_i$; jeśli istnieje wiele poprawnych permutacji, znajdź najmniejszą leksykograficznie.

Przypomnijmy, że permutacja $a$ jest mniejsza leksykograficznie od permutacji $b$ wtedy i tylko wtedy, gdy istnieje indeks $i$ ($1 \le i \le n$) taki, że $a_i < b_i$ oraz dla wszystkich $1 \le j < i$ zachodzi $a_j = b_j$.

Wejście

Pierwszy wiersz zawiera liczbę całkowitą $T$ ($1 \le T \le 5 \times 10^4$), oznaczającą liczbę przypadków testowych.

Dla każdego przypadku testowego pierwszy wiersz zawiera liczbę całkowitą $n$ ($2 \le n \le 5 \times 10^5$), oznaczającą liczbę wierzchołków w drzewie.

Drugi wiersz zawiera $n$ liczb całkowitych $d_1, d_2, \dots, d_n$ ($-1 \le d_i \le n$).

Każdy z kolejnych $n - 1$ wierszy zawiera dwie liczby całkowite $u$ oraz $v$ ($1 \le u, v \le n, u \ne v$), oznaczające krawędź łączącą wierzchołki $u$ i $v$ w drzewie.

Gwarantowane jest, że suma $n$ po wszystkich przypadkach testowych nie przekracza $5 \times 10^5$.

Wyjście

Dla każdego przypadku testowego wypisz jeden wiersz zawierający $n$ dodatnich liczb całkowitych oddzielonych spacjami, reprezentujących najmniejszą leksykograficznie poprawną permutację; lub wypisz $-1$, jeśli żadna poprawna permutacja nie istnieje.

Przykład

Wejście

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

Wyjście

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

Uwaga

Dla pierwszego przypadku testowego $p = [1, 2, 3, 4, 5]$ nie jest poprawna, ponieważ wierzchołek $2$ nie ma ważnych wierzchołków, więc $d_2 = -1 \ne 1$. Podobnie $p = [3, 4, 1, 5, 2]$ nie jest poprawna, ponieważ $d_1 = 2 \ne -1$.