Cho một cây có \(n\) nút được đánh số từ \(1\) đến \(n\). Với mỗi nút trên cây, hãy tìm khoảng cách dài nhất từ nút đó đến các nút khác.

Input

• Dòng đầu tiên chứa số nguyên dương \(n\) (\(1 \le n \le 2 \cdot 10^5\)).
• \(n-1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên dương \(a\) và \(b\) (\(1 \le a, b \le n\)), thể hiện có cạnh nối giữa nút \(a\) và nút \(b\).

Output

• In ra \(n\) số nguyên, số thứ \(i\) (\(1 \le i \le n\)) là khoảng cách dài nhất từ nút \(i\) đến các nút khác trong cây.

Example

5
1 2
1 3
3 4
3 5

2 3 2 3 3

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(n \le 10^3\).
• Subtask \(2\) (\(50\%\) số điểm): Không có ràng buộc gì thêm.