题目描述

对于一棵 $n$ 个点的无根树 $T$，点的编号为 $1,2,\cdots,n$，小 A 将其按照排列 $p_1,p_2,\cdots,p_n$ 操作以如下方式得到一棵有根树 $T'$：

1. 找到无根树 $T$ 中在排列 $p_1,p_2,\cdots,p_n$ 中出现位置最早的点 $x$。
2. 将 $x$ 从 $T$ 中删除，并往 $T'$ 中加入 $x$ 作为 $T'$ 的根。
3. $T$ 中剩下若干个连通块 $T_1,T_2,\cdots T_k$（可能 $k = 0$），每个连通块 $T_i$ 仍然是一棵无根树，对每棵无根树 $T_i$ 操作得到有根树 $T'_i$。
4. 将每棵有根树 $T'_i$ 加入 $T'$，并将 $T'_i$ 的根的父亲设为 $x$。

现在给出一棵树 $T$ 和操作排列 $p_1,p_2,\cdots,p_n$，小 A 希望得到 $T$ 按照排列 $p_1,p_2,\cdots,p_n$ 操作后得到的有根树 $T'$ 上每个点的父亲。

输入格式

第一行一个正整数 $T$（$1 \leq T \leq 10^4$），表示数据组数。

对于每组数据，第一行一个整数 $n$（$1 \leq n \leq 10^5$）表示树的点数。

第二行 $n$ 个整数 $p_1,p_2,\cdots,p_n$（$1 \leq p_i \leq n,\forall i \neq j,p_i \neq p_j$），表示排列。

接下来 $n - 1$ 行，每行两个整数 $x,y$（$1 \leq x,y \leq n,x \neq y$），表示树上的一条边。

保证单个测试点内每组数据中 $n$ 的和不超过 $10^6$。

输出格式

对于每组数据，一行 $n$ 个整数，第 $i$ 个整数表示操作后得到的有根树 $T'$ 上点 $i$ 的父亲，如果点 $i$ 为根则点 $i$ 的父亲编号为 $0$。

3
3
2 3 1
1 2
2 3
5
2 1 4 5 3
1 2
1 3
2 4
2 5
5
1 2 3 4 5
1 2
1 3
2 4
2 5

2 0 2
2 0 1 2 2
0 1 1 2 2

解释 #1

对于第一组样例，首先 $p_1 = 2$，所以 $T'$ 的根为 $2$，$T$ 分为连通块 $T_1 = \{2\}$，$T_2 = \{3\}$，于是 $2$、$3$ 在 $T'$ 上的父亲均为 $2$。

对于第二组样例，首先 $p_1 = 2$，所以 $T'$ 的根为 $2$，$T$ 分为连通块 $T_1 = \{1,3\}$，$T_2 = \{4\}$，$T_3 = \{5\}$。$T_2$、$T_3$ 都是单个点构成的树，于是 $4$、$5$ 在 $T'$ 上的父亲均为 $2$；而对于 $T_1 = \{1,3\}$，由于 $1$ 在序列 $p$ 中的出现位置更靠前（$p_2 = 1$，$p_5 = 3$），所以 $T'_1$ 的根为 $1$，于是 $1$ 在 $T'$ 上的父亲为 $2$，$3$ 在 $T'$ 上的父亲为 $1$。

对于第三组样例，首先 $p_1 = 1$，所以 $T'$ 的根为 $1$，$T$ 分为连通块 $T_1 = \{2,4,5\}$，$T_2 = \{3\}$。$T_2$ 是单个点构成的树，于是 $3$ 在 $T'$ 上的父亲为 $1$；而对于 $T_1 = \{2,4,5\}$，由于 $2$ 在序列 $p$ 中的出现位置更靠前（$p_2 = 2$，$p_4 = 4$，$p_5 = 5$），所以 $T'_1$ 的根为 $2$，于是 $2$ 在 $T'$ 上的父亲为 $1$。继续拆分 $4$、$5$ 分别构成单独子树，其在 $T'$ 上的父亲均为 $2$。