CF1611D.Weights Assignment For Tree Edges

You are given a rooted tree consisting of $n$ vertices. Vertices are numbered from $1$ to $n$. Any vertex can be the root of a tree.

A tree is a connected undirected graph without cycles. A rooted tree is a tree with a selected vertex, which is called the root.

The tree is specified by an array of ancestors $b$ containing $n$ numbers: $b_i$ is an ancestor of the vertex with the number $i$. The ancestor of a vertex $u$ is a vertex that is the next vertex on a simple path from $u$ to the root. For example, on the simple path from $5$ to $3$ (the root), the next vertex would be $1$, so the ancestor of $5$ is $1$.

The root has no ancestor, so for it, the value of $b_i$ is $i$ (the root is the only vertex for which $b_i=i$).

For example, if $n=5$ and $b=[3, 1, 3, 3, 1]$, then the tree looks like this.

An example of a rooted tree for $n=5$, the root of the tree is a vertex number $3$.

You are given an array $p$ — a permutation of the vertices of the tree. If it is possible, assign any positive integer weights on the edges, so that the vertices sorted by distance from the root would form the given permutation $p$.

In other words, for a given permutation of vertices $p$, it is necessary to choose such edge weights so that the condition $dist[p_i] \lt dist[p_{i+1}]$ is true for each $i$ from $1$ to $n-1$. $dist[u]$ is a sum of the weights of the edges on the path from the root to $u$. In particular, $dist[u]=0$ if the vertex $u$ is the root of the tree.

For example, assume that $p=[3, 1, 2, 5, 4]$. In this case, the following edge weights satisfy this permutation:

• the edge ($3, 4$) has a weight of $102$;
• the edge ($3, 1$) has weight of $1$;
• the edge ($1, 2$) has a weight of $10$;
• the edge ($1, 5$) has a weight of $100$.

The array of distances from the root looks like: $dist=[1,11,0,102,101]$. The vertices sorted by increasing the distance from the root form the given permutation $p$.

Print the required edge weights or determine that there is no suitable way to assign weights. If there are several solutions, then print any of them.

你被给定一棵包含 $n$ 个顶点的有根树。顶点编号为 $1$ 到 $n$。任意顶点均可作为树的根。

树是无环的连通无向图；有根树是选定一个顶点作为根的树。

该树由一个祖先数组 $b$（含 $n$ 个整数）给出：$b_i$ 表示编号为 $i$ 的顶点的一个祖先。顶点 $u$ 的祖先，是指从 $u$ 到根的简单路径上紧邻 $u$ 的下一个顶点。例如，在从 $5$ 到 $3$（根）的简单路径上，紧邻 $5$ 的下一个顶点是 $1$，因此 $5$ 的祖先为 $1$。

根没有祖先，故对根顶点 $i$，其 $b_i = i$（根是唯一满足 $b_i = i$ 的顶点）。

例如，若 $n=5$ 且 $b=[3, 1, 3, 3, 1]$，则该树如下图所示：

一个 $n=5$ 的有根树示例，树的根为顶点 $3$。

你被给定一个数组 $p$ —— 树中所有顶点的一个排列。若可能，请为每条边赋予任意正整数权重，使得按到根的距离升序排列的顶点序列恰好为给定排列 $p$。

换言之，对于给定的顶点排列 $p$，需选择边权，使得对每个 $i$（从 $1$ 到 $n-1$），均有 $dist[p_i] \lt dist[p_{i+1}]$ 成立。其中 $dist[u]$ 表示从根到 $u$ 的路径上所有边的权重之和。特别地，若顶点 $u$ 即为根，则 $dist[u] = 0$。

例如，设 $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$。

请输出满足要求的边权，或判定不存在可行的赋权方案。若存在多种解，输出任意一种即可。

The first line of input data contains an integer $t$ ($1 \le t \le 10^4$) — the number of input data sets in the test.

Each test case consists of three lines.

The first of them contains an integer $n$ ($1 \le n \le 2 \cdot 10^5$). It is the number of vertices in the tree.

The second line contains $n$ integers $b_1, b_2, \dots, b_n$ ($1 \le b_i \le n$). It is guaranteed that the $b$ array encodes some rooted tree.

The third line contains the given permutation $p$: $n$ of different integers $p_1, p_2, \dots, p_n$ ($1 \le p_i \le n$).

It is guaranteed that the sum of the values $n$ over all test cases in the test does not exceed $2 \cdot 10^5$.

输入数据的第一行包含一个整数 $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$。

For each set of input data print the answer on a separate line.

If the solution exists, print an array of $n$ integers $w_1, w_2, \dots, w_n$, where $w_i$ is the weight of the edge that leads from $b_i$ to $i$. For the root there is no such edge, so use the value $w_i=0$. For all other vertices, the values of $w_i$ must satisfy the inequality $1 \le w_i \le 10^9$. There can be equal numbers among $w_i$ values, but all sums of weights of edges from the root to vertices must be different and satisfy the given permutation.

If there are several solutions, output any of them.

If no solution exists, output -1.

对于每组输入数据，请在单独的一行上输出答案。

如果解存在，则输出一个包含 $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。

The first set of input data of the example is analyzed in the main part of the statement.

In the second set of input data of the example, it is impossible to assign the positive weights to obtain a given permutation of vertices.

示例的第一组输入数据在题面主体部分中进行了分析。

在示例的第二组输入数据中，无法通过赋予正权重来得到给定的顶点排列。