Fulkerson

레스터와 델버트는 철도망에서 최소 개수의 철로를 폭파해 네트워크를 끊는 방법을 이미 알고 있다. 그 문제가 꽤 쉬웠기 때문에 연방 은행을 터는 방법이라는 다음 흥미로운 문제로 넘어갔다. 이제 그들은 탈출 계획을 세우는 데 당신의 도움이 필요하다.

은행은 $N$개의 교차로와 이들을 잇는 $N - 1$개의 양방향 도로가 있는 도시에 있다. 모든 도로의 길이는 같다. 도로망을 이용하면 어떤 교차로에서든 다른 모든 교차로로 갈 수 있다.

안전한 탈출을 위해 레스터와 델버트는 $K$개의 경계 그룹을 고용해 서로 다른 교차로에 배치하고, 경찰의 움직임에 대한 정보를 수집할 계획이다. 배치가 정해지면 각 교차로마다 어떤 경계 그룹이든 도달하는 데 필요한 최소 도로 수를 구한다. 모든 교차로에 대해 이 값의 최댓값을 그 배치의 위협 수준이라고 한다.

레스터는 경계 그룹을 하나만 고용하고 싶어 하고, 델버트는 $N$개를 쓰고 싶어 한다. 결과는 대개 그 사이 어딘가에 놓일 것이므로, 가능한 $K$의 값마다 달성할 수 있는 위협 수준의 최솟값을 구하라.

입력의 첫 줄에는 도시의 교차로 수 $N$이 주어진다 ($1 \leq N \leq 150\,000$). 다음 $N-1$개의 줄에는 도로에 대한 정보가 주어진다. 각 줄에는 두 정수 $u$와 $v$가 주어지며, 이는 두 교차로 사이에 도로가 있다는 뜻이다 ($1 \le u, v \le N$, $u \neq v$). 어떤 교차로에서든 도로망을 통해 다른 모든 교차로에 도달할 수 있음이 보장된다.

출력은 $N$개의 정수로 이루어진다. $i$번째 정수는 정확히 $i$개의 경계 그룹을 사용해 달성할 수 있는 위협 수준의 최솟값과 같아야 한다.