給定一棵擁有 $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