Cut Down the Trees

Time Limit: 1 Second    Memory Limit: 32768 KB

Cutting down a virtual tree isn't quite a complicated job. Just sway your axe several times and the tree is down.

Cutting down a digital tree is not that simple. Before cutting a node, one has to deal with all of it's branches. Otherwise, data may become lost. To make this process more convenient, the International Carpenter Provision Corporation (ICPC) invented a tool called Advanced Cutting Machine (ACM). An ACM cuts down a tree in several turns. In each turn, it can cut at most k nodes (k is called the ability of that ACM). Furthermore, it can only cut a node if all of it's branches are cut in previous turns.

Given a tree, calculate the minimal turns needed for an ACM with ability k to cut it down.

Input

The input contains several cases. Each case begins with two integers n (1<=n<=100), the number of nodes in the tree, and k (k>=1), the ACM's ability. N-1 lines follow, each contains 2 integers a and b, indicating a is b's sub-node. Nodes are marked from 1 to n. There is a blank line between adjacent cases. Input is terminated by n=k=0.

Output

For each test case, output a line with the minimal turns needed.

Sample Input

4 2
2 1
3 2
4 2

0 0

Sample Output

3

Submit

Source: ZOJ Monthly, September 2003