Problem Description

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$.

Input Format

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 Format

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

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

1 2 3
-1

Hint

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