Cho một cây gồm \(n\) đỉnh.

Nhiệm vụ của bạn là với mỗi nút, hãy tìm tổng khoảng cách từ nó tới tất cả các nút khác.

Input

• Dòng đầu chứa một số nguyên \(n:\) số lượng nút. Các nút được đánh số \(1,2,... ,n\).
• Sau đó là \(n−1\) dòng mô tả các cạnh. Mỗi dòng chứa hai số nguyên \(a\) và \(b\): có một cạnh nối nút \(a\) và \(b\).

Output

• In ra \(n\) số nguyên\(:\) tổng khoảng cách từ các nút \(1,2,3,\dots,n\).

Constraints

• \(1 ≤ n ≤ 2⋅10^5\)
• \(1 ≤ a,b ≤ n\)

Example

Sample Input

5
1 2
1 3
3 4
3 5

Sample Output

6 9 5 8 8

Note

Trong Test ví dụ:

Với nút \(1\)

• Khoảng cách từ nút \(1\) tới nút \(2\) là \(1\),
• từ nút \(1\) tới nút \(3\) là \(1\),
• từ nút \(1\) tới nút \(4\) là \(2\),
• từ nút \(1\) tới nút \(5\) là \(2\)

\(\Rightarrow\) Tổng khoảng cách từ nút \(1\) tới các nút còn lại là \(1 + 1 + 2 + 2 = 6\), vậy nên ta in ra \(6\).

Tương tự với các đỉnh còn lại