Cho một cây không gốc gồm $n$ đỉnh, bạn cần gán một trọng số đôi một khác nhau cho mỗi đỉnh, với các trọng số tạo thành một hoán vị của các số từ $1$ đến $n$.
Với mỗi phương án gán, ta xét tất cả các đường kính của cây (tức là đường đi đơn dài nhất trong cây). Trong số các đường kính này, ta chọn đường kính có dãy trọng số lớn nhất theo thứ tự từ điển (sắp xếp các trọng số của các đỉnh dọc theo đường đi theo thứ tự và so sánh theo thứ tự từ điển).
Mục tiêu của bạn là cực tiểu hóa thứ tự từ điển của dãy trọng số tương ứng với "đường kính lớn nhất theo thứ tự từ điển" này trong tất cả các phương án gán có thể.
Dữ liệu vào
Một bộ kiểm tra duy nhất chứa nhiều nhóm dữ liệu.
Dòng đầu tiên của dữ liệu vào là số lượng nhóm dữ liệu $T$ ($1 \le T \le 10^5$), biểu thị số nhóm dữ liệu trong bộ kiểm tra này.
Với mỗi nhóm dữ liệu, dòng đầu tiên chứa một số nguyên $n$ ($2 \le n \le 2 \cdot 10^5$) cho biết số lượng đỉnh.
$n - 1$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u, v$ ($1 \le u, v \le n$), biểu thị một cạnh của cây.
Đảm bảo rằng trên tất cả các nhóm dữ liệu, $\sum n \le 2 \cdot 10^5$.
Kết quả
Với mỗi bộ dữ liệu, in ra một dòng gồm một số số nguyên biểu thị thứ tự từ điển nhỏ nhất có thể của đường kính có thứ tự từ điển lớn nhất.
Ví dụ
Dữ liệu vào
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
Kết quả
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