$n$ 頂点の根なし木が与えられます。各頂点に $1$ から $n$ までの順列をなす相異なる重みを割り当てる必要があります。
任意の割り当て方法について、木のすべての直径(すなわち、木内の最長単純パス)を考えます。これらの直径の中から、辞書順で最大の重み列を持つものを選択します(パス上の頂点の重みを順番に並べ、辞書順で比較します)。
あなたの目標は、すべての可能な割り当て方法の中で、この「辞書順最大の直径」に対応する重み列の辞書順を最小化することです。
入力
1 つのテストケースには複数のデータグループが含まれます。
入力の 1 行目はデータグループの数 $T$ ($1 \le T \le 10^5$) であり、このテストケースに含まれるデータグループの数を表します。
各データグループについて、1 行目には頂点数を示す整数 $n$ ($2 \le n \le 2 \cdot 10^5$) が与えられます。
続く $n - 1$ 行には、それぞれ木の辺を表す 2 つの整数 $u, v$ ($1 \le u, v \le n$) が与えられます。
すべてのデータにわたって $\sum n \le 2 \cdot 10^5$ であることが保証されます。
出力
各データセットについて、辞書順最大の直径が取り得る辞書順最小の重み列を表すいくつかの整数を 1 行に出力してください。
入出力例
入力
5 5 1 2 1 3 2 4 2 5 4 1 2 1 3 1 4 6 1 2 1 3 2 4 2 5 3 6 8 1 2 2 3 1 4 2 5 3 6 1 7 7 8 10 1 2 2 3 2 4 4 7 4 8 1 5 5 6 6 9 1 10
出力
3 4 5 1 3 4 2 3 4 5 6 1 2 3 4 5 6 1 3 4 5 6 7 8 1