Maximum Control (중간)

The Resistance은 특정 태양계에서 가능한 한 많은 행성을 장악하려 한다. Princess Heidi은 함대를 지휘하며, 장악하는 행성의 수를 최대화하기 위해 일부 행성에 함선을 보내야 한다.

The Galaxy에는 N개의 행성이 있으며, 모든 행성 쌍 사이에 유일한 경로가 존재하도록 양방향 초공간 터널로 연결되어 있다.

어떤 행성의 궤도에 Resistance 함선이 있거나, 그 행성이 궤도에 Resistance 함선이 있는 어떤 두 행성 사이의 최단 경로 위에 있으면 그 행성은 Resistance가 장악한다.

Heidi는 아직 몇 척의 함선을 사용할지 정하지 못했다. 따라서 모든 K = 1, 2, 3, ..., N에 대해, K척의 함선으로 구성된 함대로 장악할 수 있는 행성 수의 최댓값을 계산해 달라고 요청한다.

입력의 첫 번째 줄에는 은하에 있는 행성의 수를 나타내는 정수 N (1 ≤ N ≤ 105)이 주어진다.

다음 N - 1개의 줄은 행성 사이의 초공간 터널을 설명한다. Each of the N - 1개의 줄에는 공백으로 구분된 두 정수 u와 v (1 ≤ u, v ≤ N)이 주어지며, 이는 행성 u와 v 사이에 양방향 초공간 터널이 있음을 나타낸다. 임의의 두 행성이 터널 경로로 연결되어 있으며, 각 터널이 서로 다른 행성 쌍을 연결함이 보장된다.

한 줄에 공백으로 구분된 N개의 정수를 출력한다. The K-th 번째 수는 K척의 함선으로 구성된 함대를 사용하여 Resistance가 장악할 수 있는 행성 수의 최댓값이어야 한다.

첫 번째 예제를 살펴보자. If K = 1이면 Heidi는 어떤 행성 하나에 함선 한 척만 보내 그 행성을 장악할 수 있다. 하지만 K ≥ 2이면 행성 1과 3에 함선을 보내 Resistance가 모든 행성을 장악할 수 있다.