题目描述

给定一个无向图 $G$，它有 $2N$ 个节点和 $3N-2$ 条边。每条边被染成白色、黑色或红色，并满足：

• 有 $N-1$ 条白边，它们的端点都在节点集合 $\{1,2,\ldots,N\}$ 中，并形成一棵树；
• 有 $N-1$ 条黑边，它们的端点都在节点集合 $\{N+1,N+2,\ldots,2N\}$ 中，并形成一棵树；
• 有 $N$ 条红边，每条红边一端在 $\{1,\ldots,N\}$ 中，另一端在 $\{N+1,\ldots,2N\}$ 中；
• 所有红边的 $2N$ 个端点两两不同，也就是说每个节点恰好 incident 于一条红边。

称一个环为特殊哈密顿环，当且仅当：

• 它恰好访问图中每个节点一次；
• 任意连续两条边颜色不同；
• 它从节点 $1$ 开始，且第一条边为红边。

任务

输出图 $G$ 的一个特殊哈密顿环；如果不存在，则输出 -1。

输入格式

第一行包含整数 $T$，表示测试组数。

每组测试格式如下：

第一行一个整数 $N$。

接下来 $N-1$ 行，每行两个整数，表示一条白边，端点均在 $1\sim N$。

接下来 $N-1$ 行，每行两个整数，表示一条黑边，端点均在 $N+1\sim 2N$。

接下来 $N$ 行，每行两个整数，表示一条红边。

输出格式

对每组测试输出一行。

若存在特殊哈密顿环，输出 $2N$ 个整数，表示环中节点的访问顺序。

若不存在，输出 -1。

数据范围与限制

• $N\le 50000$
• $T\le 5$

子任务：

• 20 分：$N\le 10$
• 30 分：两个树均为链

样例

输入

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

输出

-1
1 7 6 4 3 5 8 2