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]<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.


-----Input-----

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$.


-----Output-----

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.


-----Examples-----

Input
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
Output
1 10 0 102 100
-1
0 3 100 1 1 2 4
6 5 10 0 2 3


-----Note-----

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.

Source: codeforces | Difficulty: MEDIUM
Tags: Tree algorithms

Constructive algorithms


Solutions:
def solution(n, parents, perm):
	res = [-1 for _ in range(len(parents))]
	temp = 0
	for (i, b) in enumerate(parents):
		if i == b:
			temp = i
			break
	res[temp] = 0
	if perm[0] != temp:
		print('-1')
		return
	for (i, p) in enumerate(perm):
		if res[parents[p]] == -1:
			print('-1')
			return
		res[p] = i
	print(' '.join((str(res[p] - res[parents[p]]) for p in range(n))))
t = int(input())
for _ in range(t):
	n = int(input())
	parents = [int(x) - 1 for x in input().split()]
	perm = [int(x) - 1 for x in input().split()]
	solution(n, parents, perm)


def solve(n, parent, permutation):
	parent_edge_weight = [0] * n
	distance = [0] * n
	processed = [False] * n
	if parent[permutation[0]] != permutation[0]:
		return (False, parent_edge_weight)
	processed[permutation[0]] = True
	lower_bound = 0
	for vertex in permutation[1:]:
		if not processed[parent[vertex]]:
			return (False, parent_edge_weight)
		processed[vertex] = True
		parent_edge_weight[vertex] = lower_bound + 1 - distance[parent[vertex]]
		distance[vertex] = lower_bound + 1
		lower_bound += 1
	return (True, parent_edge_weight)
t = int(input())
for _ in range(t):
	n = int(input())
	parent = [int(q) - 1 for q in input().split(' ')]
	permutation = [int(q) - 1 for q in input().split(' ')]
	(possible, parent_edge_weight) = solve(n, parent, permutation)
	if not possible:
		print(-1)
	else:
		print(' '.join((str(w) for w in parent_edge_weight)))


def solve():
	n = int(input())
	b = list(map(int, input().split()))
	p = list(map(int, input().split()))
	b = [x - 1 for x in b]
	p = [x - 1 for x in p]
	if p[0] != b[p[0]]:
		print(-1)
		return
	ans = [-1] * n
	dis = [0] * n
	ans[p[0]] = 0
	s = 1
	for i in range(1, n):
		if ans[b[p[i]]] < 0:
			print(-1)
			return
		dis[p[i]] = dis[p[i - 1]] + 1
		ans[p[i]] = dis[p[i]] - dis[b[p[i]]]
		s += 1
	print(' '.join((str(x) for x in ans)))
for test in range(int(input())):
	solve()


for _ in range(int(input())):
	n = int(input())
	b = list(map(int, input().split()))
	l = {int(x): i for (i, x) in enumerate(input().split())}
	r = [l[x + 1] - l[b[x]] for x in range(n)]
	print(*(r if min(r) == 0 else [-1]))


import sys
import bisect
import math
from collections import deque
input = lambda : sys.stdin.readline().strip()
mod = 10 ** 9 + 9

def solve():
	n = int(input())
	b = list(map(int, input().split()))
	p = list(map(int, input().split()))
	visited = [False] * n
	weight = [0] * n
	root = None
	for i in range(n):
		if b[i] == i + 1:
			root = i
			break
	if p[0] != root + 1:
		return -1
	visited[root] = True
	dist = [0] * n
	for i in range(1, n):
		x = p[i] - 1
		if not visited[b[x] - 1]:
			return -1
		visited[x] = True
		dist[x] = dist[p[i - 1] - 1] + 1
		weight[x] = dist[p[i - 1] - 1] - dist[b[x] - 1] + 1
	return ' '.join((str(x) for x in weight))
t = 1
t = int(input())
for _ in range(t):
	print(solve())


def solve():
	n = int(input())
	par = list(map(int, input().split()))
	per = list(map(int, input().split()))
	par = [0] + par
	per = [0] + per
	for i in range(1, n + 1):
		if par[i] == i:
			root = i
	dist = [-1] * (n + 1)
	w = [0] * (n + 1)
	dist[root] = 0
	if per[1] != root:
		print(-1)
		return
	for i in range(2, n + 1):
		node = per[i]
		p = par[node]
		if dist[p] == -1:
			print(-1)
			return
		dist[node] = i - 1
		w[node] = dist[node] - dist[p]
	print(*w[1:])
	return
for _ in range(int(input())):
	solve()


for _ in range(int(input())):
	n = int(input())
	b = [0] + list(map(int, input().split()))
	p = list(map(int, input().split()))
	if b[p[0]] != p[0]:
		print(-1)
		continue
	dist = [None] * (n + 1)
	dist[p[0]] = 0
	prev_dist = 0
	weights = [0] * n
	for i in range(1, n):
		x = p[i]
		pdist = dist[b[x]]
		if pdist is None:
			print(-1)
			break
		weights[x - 1] = max(1, prev_dist - pdist + 1)
		dist[x] = weights[x - 1] + pdist
		prev_dist = dist[x]
	else:
		print(' '.join(map(str, weights)))


def solve():
	n = int(input())
	bs = list(map(int, input().split()))
	ps = list(map(int, input().split()))
	(dist, visited, count) = ([0] * len(bs), set(), 0)
	visited.add(ps[0])
	for (arr_idx, node) in enumerate(ps):
		parent = bs[node - 1]
		if parent not in visited:
			return [-1]
		visited.add(node)
		dist[node - 1] = count
		count += 1
	ans = []
	for (idx, node_dist_from_root) in enumerate(dist):
		parent_node = bs[idx]
		parent_dist_from_root = dist[parent_node - 1]
		ans.append(node_dist_from_root - parent_dist_from_root)
	return ans
for _ in range(int(input())):
	print(*solve())


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = {int(i): j for (j, i) in enumerate(input().split())}
	for i in range(n):
		if i + 1 == a[i]:
			d = i
			break
	l = [b[i + 1] - b[a[i]] for i in range(n)]
	if min(l) != 0:
		print(-1)
	else:
		print(*l)


for h in range(int(input())):
	(n, b, l) = (input(), input().split(), {x: i for (i, x) in enumerate(input().split())})
	r = [l[str(x + 1)] - l[b[x]] for x in range(int(n))]
	print(*(r if min(r) == 0 else [-1]))


def f():
	n = int(input())
	b = list(map(int, input().split()))
	p = list(map(int, input().split()))
	for i in range(n):
		b[i] -= 1
		p[i] -= 1
	root = p[0]
	if b[root] != root:
		return [-1]
	ans = [-1] * n
	dist = [-1] * n
	d = 0
	ans[root] = 0
	dist[root] = 0
	for nod in p:
		if ans[b[nod]] == -1:
			return [-1]
		ans[nod] = d - dist[b[nod]]
		dist[nod] = d
		d += 1
	return ans
for _ in range(int(input())):
	print(*f())


import itertools
from math import floor, log, log2, ceil, sqrt
from itertools import groupby
from decimal import Decimal, getcontext
import sys
t = int(input())
res = []
for _t in range(t):
	n = int(input())
	b = list(map(int, input().split()))
	p = list(map(int, input().split()))
	b.insert(0, 0)
	p.insert(0, 0)
	ans = [-1] * (n + 1)
	distances = [0] * (n + 1)
	for i in range(1, n + 1):
		if i == 1:
			if b[p[i]] != p[i]:
				ans = [-1]
				break
			else:
				ans[p[i]] = 0
		elif ans[b[p[i]]] == -1:
			ans = [-1]
			break
		else:
			distances[p[i]] = distances[p[i - 1]] + 1
			ans[p[i]] = distances[p[i]] - distances[b[p[i]]]
	if len(ans) > 1:
		del ans[0]
	res.append(' '.join(map(str, ans)))
for i in range(t):
	print(res[i])


for _ in range(int(input())):
	n = int(input())
	b = list(map(lambda x: int(x) - 1, input().split()))
	p = list(map(lambda x: int(x) - 1, input().split()))
	d = [0] * n
	for i in range(n):
		d[p[i]] = i
	dist = [0] * n
	for i in range(n):
		if d[i] >= d[b[i]]:
			dist[i] = d[i] - d[b[i]]
		else:
			print(-1)
			break
	else:
		print(*dist)


import math
from collections import Counter, defaultdict, deque
from sys import stdin
input = stdin.readline
for _ in range(int(input())):
	n = int(input())
	b = [int(i) - 1 for i in input().split()]
	for i in range(n):
		if b[i] == i:
			rt = b[i]
			break
	p = [int(i) - 1 for i in input().split()]
	if p[0] != rt:
		print(-1)
		continue
	ans = [-1] * n
	sm = [-1] * n
	key = 0
	for (i, e) in enumerate(p):
		if i == 0:
			sm[e] = 0
			ans[e] = 0
			continue
		parent = b[e]
		if sm[parent] == -1:
			key = 1
			break
		sm[e] = i
		ans[e] = i - sm[parent]
	if key == 0:
		print(*ans)
	else:
		print(-1)


def solve(n, t, p):
	last = 0
	ans = [0] * n
	for i in range(n):
		if t[i] == i + 1:
			root = i + 1
			break
	perm = {root: 0}
	if p[0] != root:
		return [-1]
	for i in range(1, n):
		if t[p[i] - 1] not in perm:
			return [-1]
		else:
			ans[p[i] - 1] = last + 1 - perm[t[p[i] - 1]]
			last += 1
			perm[p[i]] = last
	return ans
for _ in range(int(input())):
	n = int(input())
	t = list(map(int, input().split()))
	p = list(map(int, input().split()))
	print(*solve(n, t, p))


for _ in range(int(input())):
	n = int(input())
	parents = list(map(int, input().split()))
	perm = list(map(int, input().split()))
	root = [num for (index, num) in enumerate(parents, start=1) if num == index][0]
	curr = 0
	dist = [-1] * n
	dist[root - 1] = 0
	if perm[0] != root:
		print(-1)
		continue
	ptotal = [-1] * n
	ptotal[root - 1] = 0
	for num in perm:
		if dist[parents[num - 1] - 1] == -1:
			print(-1)
			break
		dist[num - 1] = curr - ptotal[parents[num - 1] - 1]
		ptotal[num - 1] = curr
		curr += 1
	else:
		print(*dist)


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	b = list(map(int, input().split()))
	p = list(map(int, input().split()))
	b = [0] + b
	p = [0] + p
	ans = [-1 for i in range(n + 1)]
	(root, flag) = (-1, 0)
	for i in range(1, n + 1):
		if b[i] == i:
			root = i
			break
	if p[1] != root:
		print(-1)
		continue
	som = [0 for i in range(n + 1)]
	ans[p[1]] = 0
	for i in range(2, n + 1):
		if ans[b[p[i]]] == -1:
			flag = 1
			break
		som[p[i]] = i - 1
		ans[p[i]] = som[p[i]] - som[b[p[i]]]
	if flag == 1:
		print(-1)
		continue
	print(*ans[1:])


for _ in range(int(input())):
	n = int(input())
	b = list(map(int, input().split()))
	p = list(map(int, input().split()))
	root = ''
	for i in range(n):
		if i + 1 == b[i]:
			root = i + 1
			break
		else:
			continue
	if root != p[0]:
		print(-1)
		continue
	di = dict()
	for i in range(n):
		di[p[i]] = i
	weightList = list()
	flag = True
	for i in range(1, n + 1):
		child_distance = di[i]
		parent_distance = di[b[i - 1]]
		weight = child_distance - parent_distance
		if i == root or weight > 0:
			weightList.append(weight)
		else:
			flag = False
			break
	if flag == False:
		print(-1)
	else:
		print(*weightList)


t = int(input())

def solve():
	n = int(input())
	tree = [x - 1 for x in list(map(int, input().split()))]
	order = [x - 1 for x in list(map(int, input().split()))]
	if tree[order[0]] != order[0]:
		print(-1)
		return
	dist = [-1] * n
	dist[order[0]] = 0
	for i in range(1, n):
		dist[order[i]] = dist[order[i - 1]] + 1
		if dist[tree[order[i]]] > dist[order[i]] or dist[tree[order[i]]] < 0:
			print(-1)
			return
	weight = [0] * n
	for i in range(n):
		weight[i] = dist[i] - dist[tree[i]]
	print(*weight)
for _ in range(t):
	solve()


def weight(n):
	b = [None] * (n + 1)
	b[1:] = [int(j) for j in input().split()]
	p = [None] * (n + 1)
	p[1:] = [int(k) for k in input().split()]
	distance = [None] * (n + 1)
	distance[1:] = [-1] * n
	if p[1] != b[p[1]]:
		print('-1')
		return
	distance[p[1]] = 0
	for ii in range(2, n + 1):
		if distance[b[p[ii]]] == -1:
			print('-1')
			return
		distance[p[ii]] = distance[p[ii - 1]] + 1
	for jj in range(1, n + 1):
		print(distance[jj] - distance[b[jj]], end=' ')
	print()
t = int(input())
for i in range(t):
	number = int(input())
	weight(number)


from collections import defaultdict
get_int = lambda : int(input())
get_int_list = lambda : list(map(int, input().split()))

def solve():
	n = get_int()
	parent = [0] + get_int_list()
	perm = get_int_list()
	children = defaultdict(list)
	for (i, v) in enumerate(parent):
		children[v].append(i)
		if i == v:
			root = v
	valid_set = {root}
	weights = [0] * (n + 1)
	distances = [0] * (n + 1)
	next_dist = 0
	for candid in perm:
		if candid not in valid_set:
			return [-1]
		valid_set.remove(candid)
		valid_set.update(children.get(candid, []))
		par_dist = distances[parent[candid]]
		weights[candid] = next_dist - par_dist
		distances[candid] = next_dist
		next_dist += 1
	return weights[1:]
t = get_int()
for _ in range(t):
	print(' '.join(map(str, solve())))


for _ in range(int(input())):
	(n, b, l) = (int(input()), input().split(), {x: i for (i, x) in enumerate(input().split())})
	r = [l[str(x + 1)] - l[b[x]] for x in range(n)]
	print(*(r if not min(r) else [-1]))


import sys
import math
from bisect import bisect_right as br
from collections import deque

def int_arr():
	return list(map(int, sys.stdin.readline().strip().split()))

def str_arr():
	return list(map(str, sys.stdin.readline().strip().split()))

def input():
	return sys.stdin.readline().strip()
for _ in range(int(input())):
	n = int(input())
	arr = int_arr()
	p = int_arr()
	dict = {}
	for i in range(n):
		dict[p[i]] = i
	mn = 0
	ans = []
	for i in range(n):
		parent = arr[i]
		child = i + 1
		ans.append(dict[child] - dict[parent])
	if min(ans) < 0:
		print(-1)
	else:
		print(*ans)


t = int(input())
for e in range(t):
	n = int(input())
	s1 = list(map(int, input().split()))
	s2 = list(map(int, input().split()))
	ans = [-1] * n
	f = True
	if s1[s2[0] - 1] != s2[0]:
		print(-1)
		continue
	else:
		y = 0
		ans[s2[y] - 1] = 0
		while y + 1 < n:
			y += 1
			if ans[s1[s2[y] - 1] - 1] != -1:
				ans[s2[y] - 1] = ans[s2[y - 1] - 1] + 1
			else:
				print(-1)
				f = False
				break
	if f:
		ans1 = [ans[i] - ans[s1[i] - 1] for i in range(n)]
		print(*ans1)


for _ in range(int(input())):
	n = int(input())
	b = [None] + [int(x) for x in input().split()]
	p = [int(x) for x in input().split()]
	max_d = 0
	d = {p[0]: 0}
	w = [0] * (n + 1)
	for i in range(1, n):
		x = p[i]
		if b[x] not in d:
			print(-1)
			break
		d[x] = (max_d := (max_d + 1))
		w[x] = max_d - d[b[x]]
	else:
		print(*w[1:])


from collections import deque
for _ in range(int(input())):
	n = int(input())
	b = list(map(int, input().split()))
	b = [i - 1 for i in b]
	p = list(map(int, input().split()))
	p = [i - 1 for i in p]
	if p[0] != b[p[0]]:
		print(-1)
	else:
		dist = [-1 for i in range(n)]
		dist[p[0]] = 0
		flag = False
		for i in range(1, n):
			if dist[b[p[i]]] == -1:
				print(-1)
				flag = True
				break
			dist[p[i]] = dist[p[i - 1]] + 1
		if not flag:
			for i in range(0, n):
				print(dist[i] - dist[b[i]], end=' ')
			print()


def solve():
	vertex = int(input())
	parent = [-1 for i in range(vertex + 1)]
	b = list(map(int, input().split()))
	perm = list(map(int, input().split()))
	for i in range(vertex):
		parent[i + 1] = b[i]
	ongoing = 0
	done = [False for i in range(vertex + 1)]
	j = 0
	distance = [-1 for i in range(vertex + 1)]
	while j < vertex:
		if j == 0:
			if parent[perm[j]] != perm[j]:
				return [-1]
			distance[perm[j]] = ongoing
			ongoing += 1
			done[perm[j]] = True
		else:
			par1 = parent[perm[j]]
			if done[par1]:
				distance[perm[j]] = ongoing
			else:
				return [-1]
			done[perm[j]] = True
			ongoing += 1
		j += 1
	root = perm[0]
	output = [-1 for i in range(vertex + 1)]
	output[root] = 0
	for i in range(vertex):
		output[i + 1] = distance[i + 1] - distance[b[i]]
	return output[1:]
remained_test_cases = 1
remained_test_cases = int(input())
while remained_test_cases > 0:
	print(*solve())
	remained_test_cases -= 1


for _ in range(int(input())):
	n = int(input())
	par = [-1] + list(map(int, input().split()))
	per = [-1] + list(map(int, input().split()))
	dist = [-1] * (n + 1)
	w = [-1] * (n + 1)
	root = -1
	for i in range(1, n + 1):
		if par[i] == i:
			root = i
	dist[root] = 0
	w[root] = 0
	if per[1] != root:
		print(-1)
		continue
	ok = True
	for i in range(2, n + 1):
		node = per[i]
		p = par[node]
		if dist[p] == -1:
			ok = False
			break
		dist[node] = i - 1
		w[node] = dist[node] - dist[p]
	if ok:
		for i in range(n):
			print(w[i + 1], end=' ')
		print()
	else:
		print(-1)


t = int(input())
for tst in range(t):
	n = int(input())
	b = [0]
	p = [0]
	dist = [-1] * (n + 1)
	c = 0
	b += list(map(int, input().split()))
	p += list(map(int, input().split()))
	if b[p[1]] != p[1]:
		print(-1)
	else:
		dist[p[1]] = 0
		for i in range(2, n + 1):
			if dist[b[p[i]]] == -1:
				print(-1)
				c = -1
				break
			dist[p[i]] = dist[p[i - 1]] + 1
		if c != -1:
			for i in range(1, n):
				print(dist[i] - dist[b[i]], end=' ')
			print(dist[n] - dist[b[n]])


T = int(input().strip())

def find_root(parent, n):
	for i in range(n):
		if parent[i] == i:
			return i

def solve(root, dis, parent, per):
	curr_weight = 1
	dis[root] = 0
	for i in range(1, n):
		if dis[parent[per[i]]] is None or curr_weight <= dis[parent[per[i]]]:
			return False
		dis[per[i]] = curr_weight
		curr_weight += 1
	return True
for t in range(T):
	n = int(input().strip())
	parent = [int(x) - 1 for x in input().strip().split()]
	per = [int(x) - 1 for x in input().strip().split()]
	dis = [None for i in range(n)]
	root = find_root(parent, n)
	if per[0] != root:
		print(-1)
		continue
	if solve(root, dis, parent, per):
		for i in range(n):
			print(dis[i] - dis[parent[i]], end=' ')
		print()
	else:
		print(-1)


t = int(input())
for i in range(t):
	n = int(input())
	b = list(map(int, input().split()))
	p = list(map(int, input().split()))
	w = [0] * n
	dist = [-1] * n
	flag = 0
	for k in range(n):
		if p[0] == b[p[0] - 1] and k == 0:
			w[p[k] - 1] = 0
			dist[p[k] - 1] = 0
		elif dist[b[p[k] - 1] - 1] == -1:
			print(-1)
			flag = 1
			break
		else:
			w[p[k] - 1] = k - dist[b[p[k] - 1] - 1]
			dist[p[k] - 1] = k
	if flag == 0:
		print(*w)


from collections import deque
import sys, threading

def main():
	for _ in range(int(input())):
		n = int(input())
		tree = [[] for _ in range(n + 1)]
		b = list(map(int, input().split()))
		p = list(map(int, input().split()))
		p = {p[i]: i for i in range(n)}
		dists = [p[i + 1] for i in range(n)]
		root = None
		for i in range(n):
			tree[b[i]].append(i + 1)
			if b[i] == i + 1:
				root = b[i]
		weights = [0 for i in range(n)]

		def dfs(node, parent):
			if not node:
				return True
			if parent and dists[parent - 1] >= dists[node - 1]:
				return False
			if parent:
				weights[node - 1] = dists[node - 1] - dists[parent - 1]
			for v in tree[node]:
				if v == node:
					continue
				if not dfs(v, node):
					return False
			return True
		print(-1 if not dfs(root, None) else ' '.join((str(i) for i in weights)))
sys.setrecursionlimit(1 << 30)
threading.stack_size(1 << 27)
main_thread = threading.Thread(target=main)
main_thread.start()
main_thread.join()


def solve():
	n = int(input())
	s = {i: [] for i in range(n)}
	f = list(map(lambda x: int(x) - 1, input().split()))
	for (i, f) in enumerate(f):
		if i != f:
			s[f].append(i)
		else:
			root = i
	q = list(map(lambda x: int(x) - 1, input().split()))
	if q[0] != root:
		return -1
	r = [0] * n
	i = 1
	p = {a: 0 for a in s[root]}
	m = 1
	while i < n:
		if q[i] not in p:
			return -1
		r[q[i]] = m - p[q[i]]
		for a in s[q[i]]:
			p[a] = m
		m += 1
		i += 1
	return ' '.join(map(str, r))
n = int(input())
for i in range(n):
	print(solve())


for _ in range(int(input())):
	n = int(input())
	li = list(map(int, input().split()))
	ai = list(map(int, input().split()))
	for i in range(n):
		if li[i] == i + 1:
			r = i + 1
			break
	if ai[0] != r:
		print(-1)
	else:
		di = [0] * n
		b = 0
		f = 0
		for i in range(1, n):
			if di[li[ai[i] - 1] - 1] > 0 or li[ai[i] - 1] == r:
				di[ai[i] - 1] = b + 1
				b = di[ai[i] - 1]
			else:
				f = 1
				break
		if f == 1:
			print(-1)
		else:
			for i in range(n):
				print(di[i] - di[li[i] - 1], end=' ')
			print()


for _ in range(int(input())):
	n = int(input())
	anc = list(map(int, input().split()))
	p = list(map(int, input().split()))
	for i in range(n):
		anc[i] -= 1
		p[i] -= 1
	d = [-1] * n
	w = [-1] * n
	for i in range(n):
		if anc[i] == i:
			root = i
	if p[0] != root:
		print(-1)
		continue
	d[root] = 0
	done = False
	w[root] = 0
	for i in range(1, n):
		if anc[p[i]] == root:
			d[p[i]] = d[p[i - 1]] + 1
			w[p[i]] = d[p[i]]
		elif d[anc[p[i]]] == -1:
			print(-1)
			done = True
			break
		else:
			d[p[i]] = d[p[i - 1]] + 1
			w[p[i]] = d[p[i]] - d[anc[p[i]]]
	if not done:
		print(*w)


t = int(input())

def dec(x):
	return int(x) - 1
while t:
	t -= 1
	n = int(input())
	b = list(map(dec, input().split()))
	for i in range(n):
		if b[i] == i:
			root = i
			break
	p = list(map(dec, input().split()))
	if p[0] != root:
		print(-1)
		continue
	dist = [-1 for _ in range(n)]
	wt = [-1 for _ in range(n)]
	dist[root] = 0
	wt[root] = 0
	failed = False
	for i in range(1, n):
		prnt = b[p[i]]
		if dist[prnt] == -1:
			print(-1)
			failed = True
			break
		else:
			dist[p[i]] = max(dist[prnt], dist[p[i - 1]]) + 1
			wt[p[i]] = dist[p[i]] - dist[prnt]
	if not failed:
		print(*wt, sep=' ')


for _ in range(int(input())):
	n = int(input())
	b = list(map(int, input().split()))
	p = list(map(int, input().split()))
	root = None
	for (i, item) in enumerate(b):
		if i + 1 == item:
			root = item
	weights = {}
	weights[root] = 0
	possible = True
	distances = {root: 0}
	for (i, item) in enumerate(p):
		if i == 0:
			if item != root:
				possible = False
				break
		else:
			dist_so_far = distances.get(b[item - 1])
			if dist_so_far == None:
				possible = False
				break
			to_add = distances.get(p[i - 1])
			if to_add > dist_so_far:
				weights[item] = to_add - dist_so_far + 1
				distances[item] = dist_so_far + (to_add - dist_so_far) + 1
			else:
				weights[item] = 1
				distances[item] = dist_so_far + 1
	to_print = [None for _ in range(n)]
	for item in weights:
		to_print[item - 1] = weights[item]
	if possible:
		print(*to_print)
	else:
		print(-1)


for _ in range(int(input())):
	n = int(input())
	seen = [0 for i in range(n)]
	ans = [int(i) - 1 for i in input().split()]
	l = [int(i) - 1 for i in input().split()]
	flg = 1
	for i in l:
		seen[i] = 1
		if seen[ans[i]] != 1:
			flg = 0
			break
	if flg == 0:
		print(-1)
		continue
	dist = [0 for i in range(n)]
	w = [0 for i in range(n)]
	for i in range(1, n):
		w[l[i]] = dist[l[i - 1]] - dist[ans[l[i]]] + 1
		dist[l[i]] = w[l[i]] + dist[ans[l[i]]]
	for i in w:
		print(i, end=' ')
	print()


t = int(input())
from collections import deque
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	p = list(map(int, input().split()))
	d = dict()
	for i in range(n):
		d[i + 1] = a[i]
	if d[p[0]] != p[0]:
		print(-1)
	else:
		ansd = dict()
		y = 0
		c = 0
		ansd[p[0]] = c
		c += 1
		for i in range(1, n):
			if d[p[i]] in ansd:
				ansd[p[i]] = c
				c += 1
			else:
				y = 1
				break
		if y == 1:
			print(-1)
		else:
			ans = []
			for i in range(n):
				ans.append(ansd[i + 1] - ansd[d[i + 1]])
			print(*ans)


import math
from collections import defaultdict
mod = 10 ** 9 + 7

def bexp(a, b):
	res = 1
	while b:
		if b % 2:
			res = res * a % mod
			b = b - 1
		else:
			a = a * a % mod
			b = b // 2
	return res
for cases in range(int(input())):
	n = int(input())
	b = list(map(int, input().split()))
	p = list(map(int, input().split()))
	tree = [-1] * (n + 1)
	root = -1
	for i in range(0, n):
		if i + 1 != b[i]:
			tree[i + 1] = b[i]
		else:
			root = b[i]
	if p[0] != root:
		print(-1)
	else:
		prev = 0
		cnt = 1
		d = defaultdict(lambda : -1)
		dist = [0] * n
		wt = [0] * n
		d[p[0]] = 1
		f = 0
		for i in range(1, n):
			if d[b[p[i] - 1]] == -1:
				print(-1)
				f = 1
				break
			else:
				dist[p[i] - 1] = dist[p[i - 1] - 1] + 1
				wt[p[i] - 1] = dist[p[i] - 1] - dist[b[p[i] - 1] - 1]
				d[p[i]] = 1
		if f == 0:
			print(*wt)


def solve(n, tree, order):
	tree = [z - 1 for z in tree]
	adj = [[] for _ in range(n)]
	root = -1
	for i in range(n):
		if tree[i] == i:
			root = i
			continue
		adj[tree[i]].append(i)
	order = [z - 1 for z in order]
	dis = dict()
	new = set()
	dis[root] = 0
	for each in adj[root]:
		new.add(each)
	if order[0] != root:
		return [-1]
	curr = 1
	for i in order[1:]:
		if i not in new or tree[i] not in dis or dis[tree[i]] >= curr:
			return [-1]
		dis[i] = curr
		curr += 1
		for nei in adj[i]:
			new.add(nei)
	return [dis[i] - dis[tree[i]] for i in range(n)]
t = int(input())
for _ in range(t):
	n = int(input())
	tree = list(map(int, input().split()))
	order = list(map(int, input().split()))
	print(*solve(n, tree, order))


import sys
input = sys.stdin.readline
T = int(input())
for _ in range(T):
	n = int(input())
	b = list(map(int, input().split()))
	p = list(map(int, input().split()))
	w = [0] * n
	dist = [0] * n
	root = -1
	for i in range(n):
		if b[i] - 1 == i:
			root = i
			break
	edges = [[] for _ in range(n)]
	for i in range(n):
		edges[b[i] - 1].append(i)
		edges[i].append(b[i] - 1)
	set_ = {root}
	flg = True
	cnt = 0
	for t in p:
		t -= 1
		if t in set_:
			w[t] = cnt - dist[b[t] - 1]
			dist[t] = cnt
			for t2 in edges[t]:
				set_.add(t2)
		else:
			flg = False
			break
		cnt += 1
	if not flg:
		print(-1)
	else:
		print(' '.join(map(str, w)))


from sys import stdin
import math
from collections import deque
from heapq import heapify, heappop, heappush
input = stdin.readline
for _ in range(int(input())):
	n = int(input())
	childs = {i: [] for i in range(1, n + 1)}
	parents = {i: 0 for i in range(1, n + 1)}
	data = {i: -1 for i in range(1, n + 1)}
	ptotal = {i: 0 for i in range(1, n + 1)}
	ancestors = list(map(int, input().split()))
	root = None
	for (i, a) in enumerate(ancestors):
		if i + 1 == a:
			root = a
		childs[a].append(i + 1)
	permute = list(map(int, input().split()))
	(maxtillnow, okay) = (-1, True)
	if permute[0] != root:
		print(-1)
		continue
	data[root] = 0
	maxtillnow = 0
	for p in permute[1:]:
		v = data[ancestors[p - 1]]
		if v == -1:
			okay = False
			break
		else:
			data[p] = maxtillnow + 1 - ptotal[ancestors[p - 1]]
			if maxtillnow > 1000000000:
				okay = False
				break
			ptotal[p] = maxtillnow + 1
			maxtillnow += 1
	if okay:
		res = [str(data[i]) for i in range(1, n + 1)]
		print(' '.join(res))
	else:
		print(-1)


import sys

def input():
	return sys.stdin.readline().rstrip()
sys.setrecursionlimit(10000000)

def dfs(cur):
	flag = 0
	if visited[cur] == True:
		return 0
	visited[cur] = True
	for child in tree[cur]:
		if not visited[child]:
			if sol[cur] > sol[child]:
				return 1
			flag += dfs(child)
	return flag
t = int(input())
for _ in range(t):
	n = int(input())
	lst = list(map(int, input().split()))
	order = list(map(int, input().split()))
	tree = [[] for _ in range(n + 1)]
	for i in range(n):
		if i + 1 == lst[i]:
			root = i + 1
		else:
			tree[lst[i]].append(i + 1)
	sol = [0] * (n + 1)
	for i in range(n):
		sol[order[i]] = i
	visited = [False] * (n + 1)
	flag = dfs(root)
	if flag:
		print(-1)
	else:
		tmp = []
		for i in range(n):
			tmp.append(sol[i + 1] - sol[lst[i]])
		print(*tmp)


import sys
ttime = int(input())
e = []
for ccount in range(ttime):
	n = int(input())
	parents = list(map(lambda a: int(a) - 1, input().split()))
	root = -1
	for i in range(n):
		if parents[i] == i:
			root = i
	e = [[] for i in range(n)]
	for i in range(n):
		e[parents[i]].append(i)
	order = list(map(lambda a: int(a) - 1, input().split()))
	place = [0 for i in range(n)]
	w = [0 for i in range(n)]
	for i in range(n):
		place[order[i]] = i
	marked = {root}
	bad = False
	for i in range(n):
		if not order[i] in marked:
			bad = True
		w[order[i]] = i - place[parents[order[i]]]
		for x in e[order[i]]:
			marked.add(x)
	if bad:
		print(-1)
	else:
		for i in range(n):
			sys.stdout.write(str(w[i]))
			sys.stdout.write(' ')
		print('')


import math
from heapq import heappush, heappop, heapify
import random
import string
from collections import deque
from bisect import bisect, bisect_left, bisect_right, insort
import sys
input = sys.stdin.readline
S = lambda : input().rstrip()
I = lambda : int(S())
M = lambda : map(int, S().split())
L = lambda : list(M())
mod1 = 1000000000 + 7
mod2 = 998244353
for _ in range(I()):
	n = I()
	b = L()
	p = L()
	d = [0] * n
	for i in range(n):
		d[p[i] - 1] = i
	adj = [[] for i in range(n)]
	k = 0
	for i in range(n):
		if b[i] != i + 1:
			adj[i].append(b[i] - 1)
			adj[b[i] - 1].append(i)
		else:
			k = i
	ans = [0] * n

	def bfs(i):
		q = deque()
		q.append(i)
		v = [0] * n
		while q:
			r = q.popleft()
			v[r] = 1
			for j in adj[r]:
				if v[j] == 0:
					ans[j] = d[j] - d[r]
					q.append(j)
	bfs(k)
	f = 0
	for i in range(n):
		if i != k and ans[i] <= 0:
			f = 1
	if f == 1:
		print(-1)
		continue
	print(*ans)


for _ in range(int(input())):
	n = int(input())
	P = [0] + list(map(int, input().split()))
	W = [0] + list(map(int, input().split()))
	C = [set() for _ in range(n + 1)]
	for i in range(1, n + 1):
		p = P[i]
		if p == i:
			root = p
		else:
			C[p].add(i)
	ANS = [0 for _ in range(n + 1)]
	total_w = [0 for _ in range(n + 1)]
	if root != W[1]:
		print(-1)
		continue
	next_point_set = C[root]
	idx = 2
	curr_w = 0
	while next_point_set:
		cp = W[idx]
		if cp not in next_point_set:
			break
		next_point_set.remove(cp)
		next_point_set |= C[cp]
		pp = P[cp]
		curr_w += 1
		total_w[cp] = curr_w
		ANS[cp] = total_w[cp] - total_w[pp]
		idx += 1
	if next_point_set:
		print(-1)
	else:
		print(*ANS[1:])


import sys
sys.setrecursionlimit(200000)
for t in range(int(input())):
	n = int(input())
	b = [0] + list(map(int, input().split()))
	p = [0] + list(map(int, input().split()))
	pos = [0] * (n + 1)
	root = int()
	adj = list()
	for i in range(n + 1):
		adj.append([])
	for i in range(1, n + 1):
		if i == b[i]:
			root = i
		else:
			adj[b[i]].append(i)
		pos[p[i]] = i

	def dfs(f, u):
		if pos[u] < pos[f]:
			return False
		for v in adj[u]:
			if dfs(u, v) == False:
				return False
		return True
	if dfs(root, root) == False:
		print(-1)
		continue
	sum = [0] * (n + 1)
	res = [0] * (n + 1)
	last = 0
	for i in range(1, n + 1):
		if p[i] == root:
			continue
		res[p[i]] = last - sum[b[p[i]]] + 1
		sum[p[i]] = sum[b[p[i]]] + res[p[i]]
		last = sum[p[i]]
	for i in range(1, n + 1):
		print(res[i], end=' ')
	print('')


import collections
from functools import partial

def solve() -> None:
	n = int(input())
	parents = [int(i) - 1 for i in input().split()]
	edges = [set() for _ in range(n)]
	permutation = [int(i) - 1 for i in input().split()]
	for (index, parent) in enumerate(parents):
		if index == parent:
			root = index
		edges[index].add(parent)
		edges[parent].add(index)
	ancestors = [set([i]) for i in range(n)]
	discovered = set()

	def discover(index: int, ancestor: int=None) -> None:
		discovered.add(index)
		if ancestor is not None:
			ancestors[index].add(ancestor)
		for edge in edges[index]:
			if edge not in discovered:
				queue.append(partial(discover, edge, index))
	queue = collections.deque([partial(discover, root)])
	while queue:
		func = queue.popleft()
		func()
	discovered = set()
	for p in permutation:
		discovered.add(p)
		if not ancestors[p].issubset(discovered):
			print(-1)
			return
	results = [0] * n
	distances = [0] * n

	def distance(index: int) -> int:
		if index == root:
			return 0
		if distances[index] > 0:
			return distances[index]
		distances[index] = results[index] + distance(parents[index])
		return distances[index]
	for i in range(len(permutation) - 1):
		last = permutation[i]
		current = permutation[i + 1]
		results[current] = 1 + distance(last) - distance(parents[current])
	print(*results)
for _ in range(int(input())):
	solve()