Colorful Village 是一个热门的旅游目的地。它有 $2n$ 座房屋，编号从 $1$ 到 $2n$。每座房屋都有 $n$ 种颜色中的一种，编号从 $1$ 到 $n$。巧合的是，对于这 $n$ 种颜色中的每一种，恰好有两座房屋被涂成了该颜色。

Colorful Village 中有 $2n - 1$ 条双向道路。每条道路连接两座不同的房屋，并且可以通过这些道路从任意房屋到达其他任何房屋。

Catherine 计划去 Colorful Village 旅行。由于她的时间有限，她想选择一个包含 $n$ 座房屋的集合 $S$ 进行参观，且每种颜色恰好包含一座房屋。然而，由于 Catherine 还需要在房屋之间移动，她打算参观的房屋集合必须是连通的。换句话说，必须能够仅通过集合 $S$ 中的房屋，在 $S$ 中的任意两座房屋之间往返。

请帮助 Catherine 找到一个包含 $n$ 座房屋的连通集合 $S$（每种颜色各一座），或者报告不存在这样的集合。

输入格式

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$ ($1 \le t \le 10^5$)。

测试用例的描述如下：

每个测试用例的第一行包含一个整数 $n$ ($1 \le n \le 10^5$)。

第二行包含 $2n$ 个整数 $c_1, c_2, \dots, c_{2n}$，表示 Colorful Village 中房屋的颜色 ($1 \le c_i \le n$)。从 $1$ 到 $n$ 的每个整数在这行中恰好出现两次。

接下来的 $2n - 1$ 行中，第 $i$ 行包含两个整数 $u_i$ 和 $v_i$，表示第 $i$ 条道路连接的房屋 ($1 \le u_i, v_i \le 2n; u_i \neq v_i$)。

保证所有测试用例的 $n$ 之和不超过 $10^5$。

输出格式

对于每个测试用例，如果不存在所需的房屋集合，则输出一个整数 $-1$。

否则，输出 $n$ 个不同的整数 $s_1, s_2, \dots, s_n$（顺序不限），表示一个包含 $n$ 座房屋的连通集合 $S$，且每种颜色各一座 ($1 \le s_i \le 2n$)。如果存在多个答案，输出其中任意一个即可。

样例

输入 1

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

输出 1

2 3 5 7
-1