给你一棵由 $$$n$$$ 个顶点组成的有根树。顶点编号从 $$$1$$$ 到 $$$n$$$。任何顶点都可以是树的根。
树是无环的连通无向图。有根树是具有选定顶点(称为根)的树。
树由包含 $$$n$$$ 数字的祖先数组 $$$b$$$ 指定:$$$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}]$$$对于从$$$1$$$到$$$n-1$$$的每个$$$i$$$都成立。 $$$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$$$。
打印所需的边权重或确定没有合适的方法来分配权重。如果有多个解决方案,则打印其中任何一个。
输入
输入数据的第一行包含一个整数 $$$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。
示例
输入 #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
1 10 0 102 100 -1 0 3 100 1 1 2 4 6 5 10 0 2 3
注意
示例的第一组输入数据在语句的主要部分进行分析。
在示例的第二组输入数据中,不可能分配正权重以获得给定的顶点排列。