D. Расстановка весов ребер корневого дерева
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам задано корневое дерево из $$$n$$$ вершин. Вершины пронумерованы от $$$1$$$ до $$$n$$$. Корнем может быть любая из вершин.

Дерево — это связный неориентированный граф без циклов. Корневое дерево — дерево с выделенной вершиной, которую называют корнем.

Дерево задано массивом предков $$$b$$$, содержащим $$$n$$$ чисeл: $$$b_i$$$ — предок вершины с номером $$$i$$$. Предком вершины $$$u$$$ называется такая вершина, которая является следующей вершиной на простом пути от $$$u$$$ к корню. Например, на простом пути из $$$5$$$ в $$$3$$$ (корень), следующая вершина будет $$$1$$$, таким образом, предком вершины $$$5$$$ является вершина $$$1$$$.

У корня предка нет, для него в качестве $$$b_i$$$ используется значение $$$i$$$ (таким образом, корень — единственная вершина, для которой $$$b_i=i$$$).

Например, если $$$n=5$$$ и $$$b=[3, 1, 3, 3, 1]$$$, то дерево выглядит следующим образом.

Пример корневого дерева для $$$n=5$$$, корень дерева — вершина $$$3$$$.

Задан массив $$$p$$$ — перестановка вершин дерева. Если это возможно, расставьте целочисленные положительные веса на всех ребрах данного дерева так, чтобы вершины, отсортированные по увеличению расстояния от корня, образовывали заданную перестановку $$$p$$$.

Иными словами, по заданной перестановке вершин $$$p$$$ необходимо подобрать такие положительные веса рёбер, чтобы выполнялось неравенство $$$dist[p_i]<dist[p_{i+1}]$$$ для всех $$$i$$$ от $$$1$$$ до $$$n-1$$$, где $$$dist[u]$$$ — сумма весов рёбер на пути от корня до $$$u$$$. В частности, $$$dist[u]=0$$$, если вершина $$$u$$$ является корнем дерева.

Например, пусть $$$p=[3, 1, 2, 5, 4]$$$. В этом случае следующие веса ребер удовлетворяют этой перестановке:

  • ребро ($$$3, 4$$$) имеет вес $$$102$$$;
  • ребро ($$$3, 1$$$) имеет вес $$$1$$$;
  • ребро ($$$1, 2$$$) имеет вес $$$10$$$;
  • ребро ($$$1, 5$$$) имеет вес $$$100$$$.

В этом случае массив расстояний от корня имеет вид: $$$dist=[1,11,0,102,101]$$$. Если вершины отсортировать по возрастанию расстояний, то получится заданная перестановка $$$p$$$.

Выведите искомые веса рёбер или определите, что подходящего способа назначить веса не существует. Если решений несколько, то выведите любое из них.

Входные данные

В первой строке входных данных записано целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных в тесте.

Каждый набор входных данных состоит из трех строк.

В первой из них записано целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — количество вершин в дереве.

Во второй записано $$$n$$$ целых чисел $$$b_1, b_2, \dots, b_n$$$ ($$$1 \le b_i \le n$$$). Гарантируется, что массив $$$b$$$ кодирует некоторое корневое дерево.

В третьей строке задана перестановка $$$p$$$: $$$n$$$ различных целых чисел $$$p_1, p_2, \dots, p_n$$$ ($$$1 \le p_i \le n$$$).

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных в тесте не превосходит $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите ответ на отдельной строке.

Если решение существует, то выведите массив из $$$n$$$ целых чисел $$$w_1, w_2, \dots, w_n$$$, где $$$w_i$$$ — вес ребра, которое ведёт из $$$b_i$$$ в $$$i$$$. Для корня такого ребра не существует, поэтому используйте значение $$$w_i=0$$$. Для всех остальных вершин значения $$$w_i$$$ должны удовлетворять неравенству $$$1 \le w_i \le 10^9$$$. Среди значений $$$w_i$$$ могут быть равные числа, но все суммы весов ребер от корня до вершин должны быть различны и удовлетворять заданной перестановке.

Если решений несколько, выведите любое из них.

Если решения не существует, то выведите -1.

Пример
Входные данные
4
5
3 1 3 3 1
3 1 2 5 4
3
1 1 2
3 1 2
7
1 1 2 3 4 5 6
1 2 3 4 5 6 7
6
4 4 4 4 1 1
4 2 1 5 6 3
Выходные данные
1 10 0 102 100
-1
0 3 100 1 1 2 4
6 5 10 0 2 3
Примечание

Первый набор входных данных примера разобран в основной части условия.

Во втором наборе входных данных примера невозможно расставить целочисленные положительные веса так, чтобы получить заданную перестановку вершин.