题目描述

彩色村庄有 $2n$ 栋房屋，编号为 $1$ 到 $2n$。每栋房屋具有 $n$ 种颜色之一，颜色编号为 $1$ 到 $n$。恰好每种颜色都出现两次。

村庄中有 $2n-1$ 条双向道路。每条道路连接两栋不同的房屋，并且任意两栋房屋之间都可以通过这些道路互相到达，因此道路构成一棵树。

Catherine 想选择一个包含 $n$ 栋房屋的集合 $S$，并满足：

1. 每种颜色恰好选择一栋房屋；
2. 集合 $S$ 在原树中连通。也就是说，在 $S$ 中任意两栋房屋之间，都存在一条只经过 $S$ 中房屋的道路路径。

请找出这样的集合 $S$；若不存在，则报告无解。

输入格式

每个输入包含多组测试数据。

第一行包含测试数据组数 $t$（$1\le t\le 10^5$）。

对于每组测试数据：

• 第一行包含一个整数 $n$（$1\le n\le 10^5$）；
• 第二行包含 $2n$ 个整数 $c_1,c_2,\ldots,c_{2n}$，其中 $c_i$ 表示第 $i$ 栋房屋的颜色（$1\le c_i\le n$）。每个 $1$ 到 $n$ 之间的整数恰好出现两次；
• 接下来 $2n-1$ 行，每行包含两个整数 $u_i,v_i$，表示一条连接房屋 $u_i$ 和 $v_i$ 的道路（$1\le u_i,v_i\le 2n$，$u_i\ne v_i$）。

保证所有测试数据中 $n$ 的总和不超过 $10^5$。

输出格式

对于每组测试数据：

• 若不存在满足要求的集合，输出一行 -1；
• 否则输出 $n$ 个互不相同的整数 $s_1,s_2,\ldots,s_n$，顺序任意，表示一个满足要求的集合 $S$（$1\le s_i\le 2n$）。

若有多种答案，输出任意一种。

样例

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

2 3 5 7
-1