Cho một cây \(n\) đỉnh có đỉnh gốc là \(1\). Xác định độ sâu của mỗi đỉnh. Độ sâu của một đỉnh là số lượng cạnh trên đường đi từ đỉnh gốc đến nó.

Dữ liệu vào

• Dòng đầu tiên gồm số nguyên \(n\).
• \(n-1\) dòng tiếp theo, mỗi dòng gồm \(2\) số nguyên \(u,v\) có cạnh nối giữa \(u\) và \(v\).

Dữ liệu ra

• In ra \(n\) số nguyên, số nguyên thứ \(i\) là độ sâu của cạnh \(i\).

Điều kiện

• \(1 \le n \le 10^5\)
• \(1 \le u,v \le n\)

Input 1

5
1 2
1 3
3 4
3 5

Output 1

0 1 1 2 2