물류창고 2

KOPANG은 한국에서 가장 큰 온라인 판매업체 중 하나로, 이른바 "새벽 배송"을 처음으로 도입했다. 늘어나는 수요에 대응하기 위해 KOPANG은 새 물류창고를 세울 계획이다. 물류창고의 위치는 KOPANG이 고객에게 보장한 배송 시간을 지키기 위해 고객으로부터 일정 거리 이내여야 한다.

물류망은 연결된 트리 $T$로 모델링된다. $T$의 각 노드는 한국의 시나 도 같은 지역을 나타내고, $T$의 각 간선은 두 지역을 잇는 교통 도로를 나타낸다. KOPANG은 거리 제약을 만족하는 $T$의 노드를 하나 이상 골라 물류창고로 삼으려 한다. 위치를 정하기에 앞서 KOPANG은 충분한 조사를 거쳐 거리 매개변수 $K$를 먼저 정했다. 이제 KOPANG은 $T$의 모든 노드에서 가장 가까운 선택된 노드(창고)까지의 거리가 $K$ 이하가 되도록 거리 제약을 만족하는 노드를 최소 개수로 고르려 한다. 두 노드 $u$와 $v$의 거리는 $T$에서 $u$와 $v$를 잇는 (유일한) 경로의 간선 수로 정의한다. $u = v$이면 거리는 0이다.

예를 들어 아래 Figure G.1은 노드 9개와 간선 8개로 이루어진 트리 $T$를 보여 준다. $K = 1$일 때 Figure G.1 (a)처럼 노드 $2$, $5$, $8$에 빨간 원으로 표시한 세 창고를 두면 $T$의 모든 노드에서 가장 가까운 창고까지의 거리가 1 이하이다. 창고 두 개로는 거리 제약을 만족할 수 없으므로 세 개가 최소이다. $K = 2$일 때도 세 개의 창고가 필요하며, $K = 1$일 때 노드 $2$, $5$, $8$에 둔 창고가 $K = 2$일 때의 창고이다. 물론 최소 개수의 창고 위치가 유일한 것은 아니며, Figure G.1 (b)처럼 노드 $4$, $7$, $1$에 둔 세 창고도 $K = 2$에 대한 거리 제약을 만족한다.

(a)	(b)

Figure G.1 빨간 원으로 표시한 노드가 창고로 선택된 노드이다.

연결된 트리 $T$와 양의 정수 $K$가 주어질 때, 거리 제약, 즉 $T$의 모든 노드에서 가장 가까운 창고까지의 거리가 $K$ 이하가 되도록 $T$의 노드(창고)를 최소 개수로 고르는 프로그램을 작성하라.

프로그램은 표준 입력에서 입력을 읽는다. 입력의 첫 줄에는 두 정수 $n$과 $K$가 주어진다($1 ≤ K ≤ n ≤ 10^5$). $n$은 연결된 트리의 노드 수이고, $K$는 트리의 각 노드에서 가장 가까운 선택된 노드까지의 최대 거리이다. 다음 $n-1$개 줄에 간선 정보가 주어진다. $i$번째 줄에는 $i$번째 간선의 양 끝 노드의 번호를 나타내는 두 양의 정수가 주어진다. 노드 번호는 $1$부터 $n$까지이다.

프로그램은 표준 출력에 출력을 쓴다. 주어진 트리와 거리 매개변수 $K$에 대해 거리 제약을 만족하는 물류창고로 선택한 노드의 최소 개수를 한 줄에 출력한다.

처음 두 샘플은 각각 Figure G.1 (a)와 (b)에 대응한다.