Anh được cung cấp một cây gồm $n$ đỉnh. Nhiệm vụ của Anh là, với mỗi đỉnh, hãy tính tổng khoảng cách từ đỉnh đó tới tất cả các đỉnh còn lại trong cây.

Input:

• Dòng đầu tiên chứa một số nguyên $n$ $(1 \le n \le 2 \cdot 10^5)$: số lượng đỉnh trong cây. Các đỉnh được đánh số từ $1$ đến $n$.
• Tiếp theo là $n - 1$ dòng, mỗi dòng chứa hai số nguyên $a$ và $b$ $(1 \le a, b \le n)$, biểu diễn một cạnh nối giữa đỉnh $a$ và đỉnh $b$.

Output:
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$ tới tất cả các đỉnh khác trong cây.

Example
Sample Input:

5
1 2
1 3
3 4
3 5

Sample Output:

 6 9 5 8 8