俾定一樖有 $n$ 個節點嘅無根樹,你需要為每個節點分配一個互不相同嘅權值,呢啲權值構成一個由 $1$ 到 $n$ 嘅排列。
對於任意一種分配方案,我哋考慮呢樖樹嘅所有直徑(即係樹入面最長嘅簡單路徑)。喺呢啲直徑入面,我哋揀出字典序最大嘅權值序列嗰條直徑(將沿路徑嘅節點權值按順序排列並進行字典序比較)。
你嘅目標係喺所有可能嘅分配方案入面,最小化呢個「字典序最大嘅直徑」所對應嘅權值序列嘅字典序。
輸入格式
單個測試用例包含多組數據。
輸入嘅第一行係數據組數 $T$ ($1 \le T \le 10^5$),表示呢個測試用例入面嘅數據組數。
對於每組數據,第一行包含一個整數 $n$ ($2 \le n \le 2 \cdot 10^5$),表示節點數量。
接落嚟嘅 $n - 1$ 行,每行包含兩個整數 $u, v$ ($1 \le u, v \le n$),表示樹嘅一條邊。
保證喺所有數據入面,$\sum n \le 2 \cdot 10^5$。
輸出格式
對於每組數據,輸出一行若干個整數,表示字典序最大嘅直徑所能達到嘅最小字典序權值序列。
範例
輸入
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