Cho một cây gồm \(n\) đỉnh. Nhiệm vụ của bạn là với mỗi đỉnh tính tổng khoảng cách từ đỉnh đó đến tất cả các đỉnh còn lại.

Đầu vào

• Dòng đầu tiên chứa một số nguyên \(n\): số đỉnh của cây. Các đỉnh được đánh số từ 1 đến n.
• Tiếp theo có \(n - 1\) dòng, mỗi dòng gồm hai số nguyên \(a\) và \(b\), cho biết có một cạnh nối giữa đỉnh \(a\) và đỉnh \(b\).

Đầu ra

• In ra \(n\) số nguyên: với mỗi đỉnh \(1, 2, …, n\), in ra tổng các khoảng cách từ đỉnh đó đến tất cả các đỉnh còn lại.

Ràng buộc

• \(1 \le n \le 2\cdot10^5\)
• \(1 \le a, b \le n\)

Input 1

5
1 2
1 3
3 4
3 5

Output 1

6 9 5 8 8