题目描述：

在一座大型图书馆中，有一系列互相连通的书架区域，整个书架系统构成了一个拥有 n 个书架结点与 n - 1 条通道的树形结构，每个书架结点从 1~n 进行编号。

图书馆新到了一批编号从1~n 的珍贵书籍，初始时每本编号为 i 的书籍都被放置在第 ai号书架上，并且每本编号1~n的书籍都仅在一个书架上出现。

为了让图书的存放更便于读者查找，管理员需要对书架上的书籍进行重新整理。具体操作是：需要进行恰好 n - 1次调整操作，每次操作都需要选择一条尚未调整过的通道，当选择这条通道后，通道两端书架上的书籍将进行交换，随后这条通道对应的连接关系将被标记为已调整（类似在树形结构中删除这条边）。

经过 n - 1次操作后，所有的通道连接关系都完成了调整。此时，按照书籍编号从小到大的顺序，将编号 1~n的书籍所在的书架编号依次排列，就得到一个书架编号的排列 Pi。

现在请你帮助管理员计算，在最优的调整操作方案下，能得到的字典序最小的 Pi 是什么。

例如，假设有 5 个书架，初始时编号 1 - 5 的书籍分别在 2、1、3、5、4 号书架上，按照特定顺序完成所有通道的调整操作后，最终按书籍编号顺序得到的书架编号排列为 1 3 4 2 5，这个排列是所有可能结果中字典序最小的。

输入格式：

第一行一个正整数 T，表示测试案例的组数。 对于每组测试数据： 第一行一个整数 n，表示书架系统的规模。 第二行 n 个整数，第 i（1<=i<=n）个整数表示编号为 i 的书籍初始时所在的书架编号。 接下来 n - 1行，每行两个整数 x, y，表示存在一条连接 x 号书架与 y 号书架的通道。

输出格式：

对于每组测试数据，输出一行共 n 个用空格隔开的整数，表示在最优操作方案下，所能得到的字典序最小的书架编号排列 Pi。

样例：

2
10
6 2 7 8 5 10 9 1 4 3
7 4
5 7
2 4
3 4
10 5
8 10
1 5
9 10
6 8
10
2 8 1 9 6 7 5 4 10 3
6 7
2 7
5 6
3 7
1 5
9 7
10 9
8 1
4 9

1 3 2 6 7 8 10 5 9 4
1 5 8 2 3 4 6 10 9 7

提示

1<=T<=10，1<=n<=2000保证给出的是一个树。