Cho một cây có \(n\) nút được đánh số từ \(1\) đến \(n\). Với mỗi nút trên cây, hãy tính tổng khoảng cách từ nút đó đến tất cả các nút khác.

Input

• Dòng đầu tiên chứa số nguyên dương \(n\) (\(1 \le n \le 2 \cdot 10^5\)).
• \(n-1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên dương \(a\) và \(b\) (\(1 \le a, b \le n\)), thể hiện có cạnh nối giữa nút \(a\) và nút \(b\).

Output

• In ra \(n\) số nguyên, số thứ \(i\) (\(1 \le i \le n\)) là tổng khoảng cách từ nút \(i\) đến các nút khác.

Example

5
1 2
1 3
3 4
3 5

6 9 5 8 8

Constraints

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