트리의 깊이

첫 줄에 노드의 개수 n (2 이상 5000 이하) 이 주어집니다. 이어서 n-1개의 줄에 트리의 간선 u v 가 주어집니다. 노드 번호는 1번부터 n번까지입니다.

트리의 루트를 1번 노드로 할 때, 1번부터 n번까지 각 노드의 깊이를 한 줄에 하나씩 순서대로 출력하세요. 루트의 깊이는 0 입니다.

예시

입력

7
1 6
6 3
3 5
4 1
2 4
4 7

출력

0
2
2
1
3
1
2