AT_arc170_f [ARC170F] Edge Deletion 2

[problemUrl]: https://atcoder.jp/contests/arc170/tasks/arc170_f 頂点に $ 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 $ 個のテストケースが与えられるので，それぞれについて答えてください．

入力は以下の形式で標準入力から与えられる． > $ 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\ \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 $ 以下 ### Sample Explanation 1 $ 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) $ として考えられる数列のうち，辞書順最小であることが証明できます．