서브트리의 크기

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

트리의 루트를 1번 노드로 할 때, 1번부터 n번까지 각 노드를 뿌리로 하는 서브트리의 크기(자기 자신을 포함)를 한 줄에 하나씩 순서대로 출력하세요.

예시

입력

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

출력

7
1
2
3
1
3
1