Tree Allocation

A tree is one of the most widely used data structures in computer science. The structure itself is simple, but it does not fit the way a computer stores data. Memory behaves like a one dimensional array, and a tree is not one dimensional, so cache efficiency becomes a problem once the tree is placed in memory. Data that sits in the cache is read faster, so consider an allocation with good cache behaviour.

The cost of an allocation is defined as follows. Memory is split into blocks, and one block stores at most $B$ nodes of the tree. Reading data in a block brings the whole block into the cache, and every piece of data in that block is then read faster. The cost of reading node $u$ right after node $v$ is $0$ when $u$ and $v$ are in the same block, and $1$ otherwise. The cache starts empty, so the first node read on a path always costs $1$. The cost of the path $v_1, v_2, \dots, v_n$ is the sum of the costs of reading those nodes in that order. The cost of an allocation of a tree is the maximum cost over the paths that run from the root to each terminal node. A terminal node is a node with no child under the chosen root, and in a tree with a single node the root itself is the terminal node.

The figure below shows two allocations of a tree with 10 nodes when $B = 4$ and node 1 is the root. Each frame is one block. The allocation on the left costs $3$ and is not optimal. The allocation on the right reaches the optimal cost $2$.

Given a tree, compute the minimum cost of allocation when node $i$ is the root, for every node $i$.

The input contains several test cases. The first line of each test case has two integers $N$ and $B$ separated by a single space ($1 \le N \le 100000$, $1 \le B \le N$). Each of the next $N - 1$ lines contains one integer. The $i$-th integer $p_i$ ($1 \le p_i \le i$) means that node $i + 1$ and node $p_i$ are connected. The nodes are numbered from $1$ to $N$.

The last test case is followed by a line containing two zeros. That line is not a test case.

For each test case, print Case x: on its own line, where $x$ is the test case number starting from $1$. Then print $N$ lines. The $i$-th line contains the minimum cost of allocation of the given tree when node $i$ is the root.