BichSonNhat đượ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 BichSonNhat 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)\).

Example

2
1 2

1
1