P10921 Happybob's Puzzle (UBC001A)

Given a tree with $n$ vertices, where every edge has length $1$, you need to construct a permutation $p$ of $1 \sim n$ that satisfies: - For every integer $i$ with $1 \le i < n$, the length of the simple path from vertex $p_i$ to vertex $p_{i+1}$ is odd. If a solution exists, output the lexicographically smallest permutation $p$; otherwise, output $-1$.

**This problem contains multiple test cases.** The first line contains a positive integer $t$, the number of test cases. For each test case: The first line contains a positive integer $n$. The next $n - 1$ lines each contain two positive integers $u, v$, indicating that there is an edge between vertices $u$ and $v$.

Output $t$ lines. Each line contains $n$ positive integers or a single integer $-1$, representing the answer for that test case.

**Constraints** For all testdata, $1 \le t, n, \sum n \le 10^5$, and it is guaranteed that $1 \leq u, v \leq n$ and $u \neq v$. The input is guaranteed to form a tree. Here, $\sum n$ denotes the sum of $n$ over all test cases. Translated by ChatGPT 5