Tổng Khoảng Cách Từ Mỗi Điểm

Một mạng lưới gồm $n$ điểm được nối bởi $n-1$ đoạn hai chiều sao cho giữa hai điểm bất kỳ luôn có đúng một đường đi. Độ dài của một đường đi là số đoạn mà đường đi ấy sử dụng.

Với mỗi điểm $u$, hãy tính tổng độ dài đường đi từ $u$ đến tất cả $n$ điểm của mạng lưới. Khoảng cách từ $u$ đến chính nó bằng $0$.

Input

• Dòng đầu chứa số nguyên $n$.
• Mỗi dòng trong $n-1$ dòng tiếp theo chứa hai số nguyên $u$ và $v$, cho biết có một đoạn nối hai chiều giữa hai điểm đó.

Output

• In $n$ số nguyên trên một dòng. Số thứ $u$ là tổng khoảng cách từ điểm $u$ đến mọi điểm có chỉ số từ $1$ đến $n$.

Constraints

• $1\le n\le 2\cdot 10^5$.
• $1\le u,v\le n$ và $u\ne v$.
• Các đoạn nối tạo thành một cây.
• Mỗi giới hạn trên áp dụng cho một test độc lập.

Scoring

• Subtask $1$ ($50\%$ số điểm): $n\le 15$.
• Subtask $2$ ($50\%$ số điểm): Không có giới hạn bổ sung.

Example

5
1 2
2 3
2 4
4 5

8 5 8 6 9