Score: $1000$ points

问题陈述

给定一个有 $N$ 个顶点的树，顶点编号为 $1$ 到 $N$。树的第 $i$ 条边双向连接顶点 $u_i$ 和 $v_i$。

对于一个排列 $P=(P_1,\ldots,P_N)$，其中元素为 $(1,2,\ldots,N)$ 的排列，我们定义序列 $A(P)$ 如下：

• $A(P)$ 最初为空。在每个顶点 $i$ 上写上 $P_i$。
• 对于 $i=1,2,\ldots,N$ 按此顺序，执行以下操作：
  • 如果顶点 $i$ 是孤立顶点，将 $0$ 添加到 $A(P)$ 的末尾。否则，选择一个写有最小整数的相邻顶点。将选定顶点上的整数添加到 $A(P)$ 的末尾，并移除连接顶点 $i$ 和选定顶点的边。

找到所有可能的 $A(P)$ 中字典序最小的序列。

解决给定的 $T$ 个测试用例。

以上为大语言模型 kimi 翻译，仅供参考。

Problem Statement

You are given a tree with $N$ vertices numbered $1$ to $N$. The $i$-th edge of the tree connects vertices $u_i$ and $v_i$ bidirectionally.

For a permutation $P=(P_1,\ldots,P_N)$ of $(1,2,\ldots,N)$, we define the sequence $A(P)$ as follows:

• $A(P)$ is initially empty. Write $P_i$ on each vertex $i$.
• For $i=1,2,\ldots,N$ in this order, perform the following:
  • If vertex $i$ is an isolated vertex, append $0$ to the end of $A(P)$. Otherwise, select the adjacent vertex with the smallest written integer. Append the integer written on the selected vertex to the end of $A(P)$ and remove the edge connecting vertex $i$ and the selected vertex.

Find the lexicographically smallest sequence among all possible $A(P)$.

Solve each of the $T$ given test cases.

Constraints

• $1 \leq T \leq 10^5$
• $2 \leq N \leq 2 \times 10^5$
• $1\leq u_i,v_i\leq N$
• The given graph is a tree.
• All input numbers are integers.
• The sum of $N$ over all test cases in a single input is at most $2 \times 10^5$.

Input

The input is given from Standard Input in the following format:

$T$

$\mathrm{case}_1$

$\vdots$

$\mathrm{case}_T$

Each case is given in the following format:

$N$

$u_1$ $v_1$

$u_2$ $v_2$

$\vdots$

$u_{N-1}$ $v_{N-1}$

Output

Print $T$ lines. The $i$-th line $(1 \leq i \leq T)$ should contain the answer for the $i$-th test case.

Sample Input 1

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

Sample Output 1

1 2 0 1 3
1 2 2 3 1 4 0 0
1 2 2 0 3 0 4

In the first test case, for $P=(4,1,2,3,5)$, one can obtain $A(P)=(1,2,0,1,3)$ as follows:

• The vertex adjacent to vertex $1$ with the smallest written integer is vertex $2$. Append $P_2=1$ to the end of $A(P)$ and remove the edge connecting vertices $1$ and $2$.

• The vertex adjacent to vertex $2$ with the smallest written integer is vertex $3$. Append $P_3=2$ to the end of $A(P)$ and remove the edge connecting vertices $2$ and $3$.

• Vertex $3$ is an isolated vertex, so append $0$ to the end of $A(P)$.

• The vertex adjacent to vertex $4$ with the smallest written integer is vertex $2$. Append $P_2=1$ to the end of $A(P)$ and remove the edge connecting vertices $4$ and $2$.

• The vertex adjacent to vertex $5$ with the smallest written integer is vertex $4$. Append $P_4=3$ to the end of $A(P)$ and remove the edge connecting vertices $5$ and $4$.

It can be proved that this is the lexicographically smallest sequence among all possible $A(P)$.