I. The Dream-Quest
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output
And it's too late

The damage is done

The damage is done

— Radiohead, Daydreaming

$$$~\\$$$

Three times Vistar dreamed of the marvellous jewel, and three times was he snatched away while still he paused on the high terrace above it.

Each vision just ending the same way... In dreaming, Vistar had spent months planning the ultimate theft — to steal the Legendary Jewel of Mathematical Truth, a gem said to grant its wielder infinite knowledge.

The jewel was kept atop the Crown of Proofs, guarded by the relentless Math Police, an elite order devoted to protecting the foundations of mathematics. Their stronghold is The Tree of Mathematics, a rooted tree with $$$n$$$ nodes, where every branch represented a different field — number theory, graph theory, topology, and beyond.

On the grand night, Vistar infiltrated the root (node $$$1$$$). But as he reached for the jewel, an alarm echoed through the tree. Immediately, he found himself surrounded by the guards — At every leaf of this tree stood a Math Police officer, armed with Group Theory Rifles and Algebra Theory Snipers, determined to stop him from stealing the jewel atop the Crown of Proofs.

The scene was so vivid and clear:

  • Each turn, Vistar could move one step to an adjacent node (or choose to stay);

  • Then, all officers would simultaneously move one step along their respective shortest paths toward the root. If an officer was already on the root, then he would stay still;

  • If at any moment (for example, when Vistar has finished moving but the officers have not) Vistar shared a node with any officer, the chase ends — and so does his freedom.

Waking in a cold sweat, Vistar couldn't shake the question: Under such a siege, was escape even possible? We define escape as possible if Vistar isn't captured after $$$n$$$ turns.

Since he is in a panic, he wants you to answer the question.

Input

The first line contains the number of test cases $$$T$$$ $$$(1\le T\le 1000)$$$ — the number of test cases.

The first line of each test case contains a single integer $$$n$$$ $$$(2\le n\le 2000)$$$.

Each of the next $$$n-1$$$ lines contains two integers $$$u$$$ and $$$v$$$ $$$(1\le u,v\le n, u\neq v)$$$, denoting the two vertices connected by an edge. It is guaranteed that the given edges form a tree.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2000$$$.

Output

For each test case, output $$$n$$$ numbers $$$p_1, p_2, \dots, p_n$$$ representing the position of Vistar for the first $$$n$$$ moments if he can escape. Otherwise, output $$$-1$$$. If there exist multiple answers, output any of them.

Example
Input
2
10
1 2
1 3
3 4
4 5
5 6
6 7
7 8
3 9
9 10
5
5 1
4 1
3 1
2 1
Output
1 3 4 4 3 9 10 10 10 10
-1
Note

A possible escape route for the first test case is shown below: