개의 정점으로 이루어진 트리 가 주어진다. 정점에는 의 번호가 붙어 있다.
정점 와 음이 아닌 정수 를 고른다. 와의 거리가 이하인 모든 정점과 그 정점에 연결된 모든 간선을 트리에서 제거한다. 여기서 두 정점 사이의 거리는 두 정점을 잇는 단순 경로에 포함된 간선의 개수이다.
각 정점 에 대하여, 제거한 뒤 남은 그래프의 연결 컴포넌트가 개 이상이 되게 하는 최소의 를 구하여라. 그러한 가 없다면 을 구한다.
빈 그래프의 연결 컴포넌트 개수는 이다.
입력은 다음과 같은 형식으로 주어진다.
각 정점 의 답을 라고 하자. 첫째 줄에 을 공백으로 구분하여 출력한다.
유일한 정점을 제거하면 빈 그래프가 되므로 연결 컴포넌트가 개 이상이 될 수 없다.
번 정점과 번 정점은 자기 자신만 제거해도 트리가 두 컴포넌트로 나뉜다. 두 리프에서는 어떤 를 골라도 두 컴포넌트 이상이 남지 않는다.
각 ()에 대하여 번 정점과 번 정점을 잇는 간선이 존재한다.
