Problema C - Missão de Espionagem

Os caminhos de Montemor são um conjunto de N castelos unidos por N-1 estradas bidirecionais que são tais que há pelo menos um caminho entre quaisquer dois castelos.

Para garantir que os seus súbditos não estão a planear uma revolta, o rei decidiu estacionar espiões nalguns dos castelos. Cada castelo pode ter no máximo um espião e, para garantir que ninguém desconfia, o número de espiões em cada caminho simples não deve exceder T. Um caminho simples é uma sequência de castelos v₁, v₂, ... , v_k distintos tal que existe uma estrada entre dois vértices consecutivos da sequência.

O rei quer estacionar o maior número de espiões possível que respeitam as condições acima, consegues ajudá-lo?

O Problema

Dados N-1 pares de inteiros representando estradas entre castelos e um inteiro T, determinar o maior número de espiões que podem ser colocados.

Input

A primeira linha contém dois inteiros, N, representando o número de castelos, e T, que representa o número máximo de espiões por caminho simples.

Seguem-se N-1 linhas, cada uma contendo um par de inteiros distintos entre 1 e N, que representam uma estrada entre dois castelos.

Output

O output deve conter um inteiro representando o maior número de espiões que podem ser colocados.

Restrições

São garantidos os seguintes limites em todos os casos de teste que irão ser colocados ao programa:

Os casos de teste deste problema estão organizados em 4 grupos com restrições adicionais diferentes:

Input do Exemplo 1

5 2
1 2
2 3
3 4
3 5

Output do Exemplo 1

3

Explicação do Exemplo 1

Podemos estacionar um espião nos castelos 1, 4 e 5.

Input do Exemplo 2

10 4
2 8
3 4
9 10
7 6
2 7
5 2
3 8
1 9
10 4

Output do Exemplo 2

5