서울과학고 쪼개기

서울의 명소 서울과학고등학교는 $1$부터 $N$까지 번호가 매겨진 정점이 $N - 1$개의 간선으로 연결된 트리다. 학교의 어떤 두 정점 사이도 간선을 따라 오갈 수 있다.

상훈이는 리프라서 서울과학고에 새로운 리프 노드를 추가하려고 한다. 이를 위해 학교의 임의의 정점을 골라 새 정점을 간선으로 연결한다.

성현이는 서울과학고의 정점을 "터트린다". 규칙은 다음과 같다.

• 성현이는 한 번에 한 정점만 터트릴 수 있다.
• 정점 하나를 터트리면, 그 정점으로부터의 거리가 1 이하인 정점들과 그 정점들에 연결된 간선들이 모두 삭제된다. 두 정점 사이의 거리는 한 정점에서 다른 정점으로 이동할 때 거쳐야 하는 최소 간선 개수다. 터트린 뒤에는 학교가 여러 개의 트리로 나뉠 수 있다.
• 한 번 터지거나 제거된 정점은 다시 터트릴 수 없다.
• 성현이는 학교 전체가 사라질 때까지 이 과정을 반복한다.

상훈이가 새 정점을 어디에 연결했는지 알 수 없으므로, 성현이는 가능한 모든 경우에 대비하려고 한다. 정점을 터트리는 일은 매우 힘들기 때문에, 성현이는 최소 횟수로 작업을 끝내려고 한다. 상훈이가 정점 $1$, 정점 $2$, $\cdots$, 정점 $N$에 새 정점을 연결했을 때 성현이가 터트려야 하는 정점 수의 최솟값을 구하라. 각 연결 상황은 서로 독립이다.

첫 번째 줄에 $N$이 주어진다.

두 번째 줄부터 $N-1$개의 줄 중 $i$번째 줄에는 $i$번째 간선의 양 끝점 $u_i$, $v_i$가 공백으로 구분되어 주어진다. 이는 $u_i$번 정점과 $v_i$번 정점을 잇는 간선이 있다는 뜻이다. ($1 \leq i \leq N-1$)

$N$개의 줄을 출력한다. $i$번째 줄에는 상훈이가 $i$번 정점에 새 정점을 연결했을 때 성현이가 터트려야 하는 정점 수의 최솟값을 출력한다.

• $1 \leq N \leq 300\,000$
• $1 \leq u_i, v_i \leq N$ (단, $1 \leq i \leq N-1$)