分数: 1000 点
问题陈述
你有一棵树 N 顶点编号 1 to N。的 i树的第一条边连接顶点 u_i 和 v_i 双向。
对于排列 P=(P_1,\ldots,P_N) of (1,2,\ldots,N),我们定义序列 A(P) 如下:
- A(P) 最初是空的。写 每个顶点上的 P_i 在每个顶点上 i.
- 对于 i=1,2,\ldots,N 按此顺序执行以下操作:
- 如果顶点 i 是一个孤立的顶点,追加 0 到年底 A(P)。否则,选择具有最小写入整数的相邻顶点。将写入所选顶点的整数附加到末尾 A(P) 并删除连接顶点的边 i 和选定的顶点。
在所有可能的序列中找到字典顺序最小的序列 A(P).
解决每个问题 T 给出的测试用例。
约束
- 1 \leq T \leq 10^5
- 2 \leq N \leq 2 \times 10^5
- 1\leq u_i,v_i\leq N
- 给定的图是一棵树。
- 所有输入数字均为整数。
- 总和 一个输入文件中的 N 单个输入中的所有测试用例最多 2 \times 10^5.
输入
输入由标准输入按以下格式给出:
T
\mathrm{case}_1
\vdots
\mathrm{case}_T
每个案例均按以下格式给出:
N
u_1 v_1
u_2 v_2
\vdots
u_{N-1} v_{N-1}
输出
打印 T 行。的 i第行 (1 \leq i \leq T) 应包含以下问题的答案 i- 第一个测试用例。
示例输入 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
示例输出 1
1 2 0 1 3 1 2 2 3 1 4 0 0 1 2 2 0 3 0 4
在第一个测试用例中,对于 P=(4,1,2,3,5),可以获得 A(P)=(1,2,0,1,3) 如下:
-
与顶点相邻的顶点 1 最小的写入整数是顶点 2。追加 P_2=1 到年底 A(P) 并删除连接顶点的边 1 和 2.
-
与顶点相邻的顶点 2 最小的写入整数是顶点 3。追加 P_3=2 到年底 A(P) 并删除连接顶点的边 2 和 3.
-
顶点 3 是一个孤立的顶点,所以追加 0 到年底 A(P).
-
与顶点相邻的顶点 4 最小的写入整数是顶点 2。追加 P_2=1 到年底 A(P) 并删除连接顶点的边 4 和 2.
-
与顶点相邻的顶点 5 最小的写入整数是顶点 4。追加 P_4=3 到年底 A(P) 并删除连接顶点的边 5 和 4.
可以证明这是所有可能序列中字典序最小的序列 A(P).