Tý có một hệ thống \(N\) trạm phát sóng được kết nối với nhau bằng \(N - 1\) đường truyền cáp quang tạo thành một cây. Người ta muốn chọn một trạm làm trung tâm điều phối. Chi phí vận hành khi đặt trung tâm tại trạm \(u\) là tổng khoảng cách từ \(u\) đến tất cả các trạm khác.

Với mỗi trạm \(u\), hãy tính tổng khoảng cách từ \(u\) đến tất cả các trạm còn lại trong mạng lưới.

Định dạng đầu vào

• Dòng 1: Số nguyên \(N\) (\(1 \le N \le 10^5\)).
• \(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\)) mô tả một cạnh nối giữa trạm \(u\) và trạm \(v\).

Định dạng đầu ra

• In ra \(N\) số nguyên trên một dòng, số thứ \(i\) là tổng khoảng cách từ đỉnh \(i\) đến tất cả các đỉnh còn lại.

Ví dụ

Input:

4
1 2
2 3
2 4

Output:

5 3 5 5

Giải thích: Từ đỉnh 2: \(\text{dist}(2, 1) = 1, \text{dist}(2, 3) = 1, \text{dist}(2, 4) = 1 \implies\) tổng \(= 3\).

Ràng buộc & Subtasks