Happybob's Puzzle (UBC001A)
题目描述
给定一棵有 $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$，表示该组测试数据的答案。
输入输出样例
输入样例 #1
2
3
1 2
2 3
7
1 2
1 3
2 4
2 5
3 6
3 7输出样例 #1
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$ 的总和。