F - Edge Deletion 2 Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 1000 点

問題文

頂点に 1 から N の番号が付いた N 頂点の木が与えられます．木の i 番目の辺は頂点 u_i と頂点 v_i を双方向に結んでいます．

(1,2,\ldots,N) の順列 P=(P_1,\ldots,P_N) に対し，数列 A(P) を以下で定義します．

  • A(P) は初め空である．全ての頂点 i に P_i を書き込む．
  • i=1,2,\ldots,N の順に以下を行う．
    • 頂点 i が孤立点の場合，0 を A(P) の末尾に追加する．そうでない場合，頂点 i に隣接する頂点であって，書かれている整数が最も小さいものを選ぶ．選んだ頂点に書かれた整数を 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
  • 与えられるグラフは木である
  • 入力される数値は全て整数
  • 1 つの入力に含まれるテストケースについて，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

1 番目のテストケースでは，P=(4,1,2,3,5) に対し，A(P)=(1,2,0,1,3) は以下の方法で得られます．

  • 頂点 1 に隣接する頂点であって，書かれている整数が最も小さいものは頂点 2 である．A(P) の末尾に P_2=1 を追加し，頂点 1 と頂点 2 を結ぶ辺を削除する．

  • 頂点 2 に隣接する頂点であって，書かれている整数が最も小さいものは頂点 3 である．A(P) の末尾に P_3=2 を追加し，頂点 2 と頂点 3 を結ぶ辺を削除する．

  • 頂点 3 は孤立点なので，A(P) の末尾に 0 を追加する．

  • 頂点 4 に隣接する頂点であって，書かれている整数が最も小さいものは頂点 2 である．A(P) の末尾に P_2=1 を追加し，頂点 4 と頂点 2 を結ぶ辺を削除する．

  • 頂点 5 に隣接する頂点であって，書かれている整数が最も小さいものは頂点 4 である．A(P) の末尾に P_4=3 を追加し，頂点 5 と頂点 4 を結ぶ辺を削除する．

これが A(P) として考えられる数列のうち，辞書順最小であることが証明できます．

Score: 1000 points

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).