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\).

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.

Constraints

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

Example

Sample Input

5
1 2
1 3
3 4
3 5

2 3 2 3 3