The damage is done
The damage is done
$$$~\\$$$
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:
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.
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$$$.
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.
2101 21 33 44 55 66 77 83 99 1055 14 13 12 1
1 3 4 4 3 9 10 10 10 10 -1
A possible escape route for the first test case is shown below:
| Name |
|---|


