Có \(N\) hòn đảo, đánh số từ \(1\) đến \(N\), mỗi đảo có một chú hải ly sinh sống. Các đảo được nối bởi \(N-1\) cây cầu hai chiều, đánh số từ \(1\) đến \(N-1\). Cầu \(i\) nối đảo \(A_i\) với đảo \(B_i\). Có thể đi giữa hai đảo bất kỳ qua các cây cầu.

Thỉnh thoảng, hải ly ở một số đảo tụ họp tại một đảo để tổ chức cuộc họp. Khi danh sách tham dự đã được xác định, địa điểm họp được chọn trong các đảo thỏa mãn:

Tổng số cây cầu mà những người tham dự phải đi qua để đến đảo được chọn là nhỏ nhất.

Mỗi người tham dự đi từ đảo mình sống đến địa điểm họp bằng hành trình qua ít cầu nhất.

Những người tham dự càng mong chờ cuộc họp nếu có nhiều địa điểm có thể được chọn. Khi danh sách tham dự đã cố định, độ mong chờ của cuộc họp là số đảo có thể làm địa điểm họp và thỏa mãn điều kiện tối thiểu hóa tổng số cầu ở trên.

Với mỗi số nguyên \(j\) từ \(1\) đến \(N\), hãy tìm độ mong chờ lớn nhất trong các cuộc họp có đúng \(j\) hải ly tham dự.

Cho thông tin các đảo và cầu, hãy tính giá trị đó cho mọi số lượng người tham dự.

Dữ liệu vào

Đọc từ đầu vào chuẩn theo định dạng sau. Mọi giá trị đều là số nguyên.

N
A_1 B_1
...
A_{N-1} B_{N-1}

Dữ liệu ra

In \(N\) dòng. Dòng thứ \(j\) (\(1\le j\le N\)) chứa độ mong chờ lớn nhất của một cuộc họp có \(j\) người tham dự.

Ràng buộc

• \(1\le N\le200000\).
• \(1\le A_i,B_i\le N\) với mọi \(1\le i\le N-1\).
• \(A_i\ne B_i\) với mọi \(1\le i\le N-1\).
• Có thể đi giữa hai đảo bất kỳ qua các cây cầu.

Phân nhóm

• Nhóm 1 (4 điểm): \(N\le16\).
• Nhóm 2 (16 điểm): \(N\le4000\).
• Nhóm 3 (80 điểm): Không có ràng buộc bổ sung.

Ví dụ

5
1 2
2 3
4 2
3 5

1
4
1
2
1

7
1 2
2 3
3 4
4 5
2 6
3 7

1
5
1
3
1
2
1

Nguồn

JOI 2020/2021, kỳ thi tuyển chọn mùa xuân, ngày thi thứ 3. Đề của Ủy ban Olympic Tin học Nhật Bản (JCIOI). Bản dịch tiếng Việt theo giấy phép CC BY-SA 4.0.