Bạn được cho một cây có \(n\) nút.

Nhiệm vụ của bạn là xác định khoảng cách xa nhất từ mỗi nút đến một nút khác.

Input

• Dòng đầu tiên chứa một số nguyên \(n\): số lượng nút. Các nút được đánh số \(1,2,...,n\)
• Tiếp theo là \(n-1\) dòng mô tả các cạnh. Mỗi dòng chứa hai số nguyên \(a\) và \(b\): có một cạnh nối hai nút \(a\) và \(b\)

Constraints

• \(1 \leq n \leq 2\cdot 10^5\)
• \(1 \leq a,b \leq n\)

Output

• In ra \(n\) số nguyên: với mỗi nút \(1,2,...,n\), in ra khoảng cách xa nhất đến một nút khác

Example

5
1 2
1 3
3 4
3 5

2 3 2 3 3