题目描述

给定一棵有 $n$ 个点的树，每条边的长度都是 $1$，你需要构造一个 $1\sim n$ 的排列 $p$，满足以下条件：

• 对于每个满足 $1\le i<n$ 的整数 $i$，点 $p_i$ 到点 $p_{i+1}$ 的简单路径长度为奇数。

如果有解，请输出字典序最小的排列 $p$；否则，输出 $-1$。

输入格式

本题有多组测试数据。

第一行，一个正整数 $t$，表示测试数据组数。

对于每组测试数据：

第一行，一个正整数 $n$。

接下来的 $n-1$ 行，每行两个正整数 $u,v$，表示点 $u,v$ 之间有一条边。

输出格式

$t$ 行，每行 $n$ 个正整数或一个整数 $-1$，表示该组测试数据的答案。

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

1 2 3
-1

提示

数据范围

对于所有数据，都有 $1\le t,n,\sum n\le 10^5$，保证有 $1 \leq u, v \leq n$ 且 $u \neq v$。保证输入构成一棵树。其中 $\sum n$ 表示所有测试数据的 $n$ 的总和。