Background

$\large{\bf{\textcolor{red}{Warning: Abusing the judging system for this problem may get your account banned, even after just once, and may also result in an IP ban.}}}$

$\large{\bf{\textcolor{red}{Several people have already received school disciplinary actions due to related behavior. Learn from others’ mistakes.}}}$

Due to differences in judge machine performance, the time limit is reduced by $5$ seconds.

Problem Description

Given a tree with $n$ vertices (where $n > 2$), with vertices numbered from $1$ to $n$, its Prüfer sequence is a uniquely determined sequence of length $n - 2$, which can be obtained by the following simple algorithm:

While the tree has more than two vertices:

• Find the vertex with degree $1$ that has the smallest label.
• Append the label of its only neighbor to the sequence.
• Delete this vertex from the tree.

It can be proven that every sequence of length $n - 2$ consisting of numbers between $1$ and $n$ is the Prüfer sequence of some tree, and the Prüfer sequence uniquely determines the tree it comes from. For these and other interesting facts about Prüfer sequences, you may refer to OI-wiki or other materials.

In this problem, we are given a tree and consider the Prüfer sequences generated by different ways of labeling its vertices. If $S$ is a labeling of vertices (formally, an injective function from the vertex set to the set $\{1,\dots,n\}$), then let $K(S)$ denote the Prüfer sequence of the tree under this labeling.

Your task is to find the lexicographically smallest Prüfer sequence of the given tree, i.e. find a labeling $S$ such that the sequence equals $K(S)$, and for any other labeling $S'$, either $K(S) = K(S')$, or at the first position where $K(S)$ and $K(S')$ differ, the value in $K(S')$ is larger.

You need to solve this problem for $t$ independent test cases.

Input Format

The first line contains an integer $t$ ($1 \leq t \leq 1000$), the number of test cases.

Each test case starts with a line containing an integer $n$ ($3 \leq n \leq 1000$), the number of vertices in the tree. The vertices are numbered from $1$ to $n$, but this numbering does not necessarily correspond to the lexicographically smallest Prüfer sequence.

The next $n - 1$ lines describe the edges of the tree. Each line contains two integers $a_i$ and $b_i$ ($1 \leq a_i, b_i \leq n,\ a_i \neq b_i$), indicating an edge between vertex $a_i$ and vertex $b_i$.

The sum of $n$ over all test cases does not exceed 5000.

Output Format

Output $t$ lines, one for each test case. For the $i$-th line, output a sequence of length $n - 2$, which is the lexicographically smallest Prüfer sequence of the tree in the $i$-th test case under an optimal vertex labeling.

2
5
1 2
2 3
3 4
3 5
16
8 1
9 1
10 1
11 2
12 2
2 3
13 4
4 3
14 5
15 5
5 3
3 1
1 6
6 7
7 16

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

Hint

Sample Explanation

In the first test case, an example of a vertex labeling that yields the lexicographically smallest Prüfer sequence is $1 \to 5$, $2 \to 2$, $3 \to 1$, $4 \to 4$, $5 \to 3$.
With this labeling, in the first step of the Prüfer sequence algorithm, it will choose the vertex whose new label is $3$ (and append $1$ to the sequence, i.e. the new label of its only neighbor). In the second step, it will choose the vertex whose new label is $4$ (its only neighbor is also $1$). In the third step (after deleting vertices $3$ and $4$), vertex $1$ has become a leaf and will be chosen, and the label of its neighbor, $2$, will be appended as the last element of the sequence.
In the second test case, the optimal solution is to not relabel the vertices at all. Also, the order of edges in the input matches the order in which the Prüfer sequence algorithm deletes leaf vertices.

Translated by ChatGPT 5