ShyWoou được thầy giáo cho một cây gồm $n$ đỉnh và $n-1$ cạnh.

Thầy giáo định nghĩa $d(i, j)$ là số cạnh tối thiểu để duyệt từ đỉnh $i$ đến đỉnh $j$.

Với mỗi đỉnh $i$ trên đồ thị, thầy giáo yêu cầu ShyWoou hãy tính :

• $\sum_{i = 1}^{n}\sum_{j = 1}^{n} d(i, j)$

Input

• Dòng đầu chứa số nguyên dương $n$ $(2 ≤ n ≤ 2\times10^5).$
• $N-1$ dòng tiếp theo chứa hai số nguyên dương $u_i$ và $v_i(1 \leq u_i < v_i \leq n)$, giữa hai đỉnh $u_i$ và $v_i$ có cạnh nối vô hướng.

Output

• Gồm $n$ dòng, dòng thứ $i$ in ra $\sum_{j = 1}^{n} d(i, j)$.

Ví dụ

Sample Input

2
1 2

Sample Output

1
1

Giải thích

• Với $i = 1$, ta có $d(1, 1) + d(1, 2) = 0 + 1 = 1$.
• Với $i = 2$, ta có $d(2, 1) + d(2, 2) = 1 + 0 = 1$.