트리 배치

트리는 컴퓨터 과학에서 널리 쓰는 자료구조이다. 트리 구조 자체는 단순하지만 오늘날의 컴퓨터 구조와는 잘 맞지 않는다. 메모리는 1차원 배열로 볼 수 있는데 트리는 1차원 구조가 아니라서, 트리를 메모리에 올릴 때 캐시 효율이 문제가 된다. 캐시에 들어 있는 데이터는 더 빨리 읽는다. 캐시 성능이 좋은 배치를 생각해 보자.

배치 비용은 다음과 같이 정의한다. 메모리는 블록으로 나뉘고, 한 블록에는 트리의 노드를 최대 $B$개까지 저장한다. 어떤 블록의 데이터를 읽으면 그 블록의 데이터가 모두 캐시에 올라가고, 그 블록에 속한 데이터는 더 빨리 읽는다. 노드 $v$를 읽은 다음 노드 $u$를 읽는 비용은 $u$와 $v$가 같은 블록에 있으면 $0$, 아니면 $1$이다. 처음에 캐시는 비어 있으므로 경로에서 맨 처음 읽는 노드의 비용은 항상 $1$이다. 경로 $v_1, v_2, \dots, v_n$의 비용은 이 순서대로 노드를 읽을 때 드는 비용의 합이다. 트리의 배치 비용은 루트에서 각 단말 노드까지 가는 경로의 비용 중 최댓값이다. 단말 노드는 루트를 기준으로 자식이 없는 노드이고, 노드가 하나뿐인 트리에서는 루트가 곧 단말 노드이다.

아래 그림은 노드가 10개인 트리를 $B = 4$, 노드 1을 루트로 두고 배치한 예이다. 테두리 하나가 블록 하나를 나타낸다. 왼쪽 배치는 비용이 $3$이라서 최적이 아니고, 오른쪽 배치는 최적 비용 $2$를 달성한다.

트리가 주어질 때, 각 노드 $i$를 루트로 삼았을 때의 최소 배치 비용을 구하라.

입력은 여러 테스트 케이스로 이루어진다. 각 테스트 케이스의 첫 줄에는 정수 $N$과 $B$가 공백 하나를 사이에 두고 주어진다 ($1 \le N \le 100000$, $1 \le B \le N$). 다음 $N - 1$개의 줄에는 정수가 하나씩 주어진다. $i$번째 정수 $p_i$ ($1 \le p_i \le i$)는 노드 $i + 1$과 노드 $p_i$가 연결되어 있다는 뜻이다. 노드 번호는 $1$번부터 $N$번까지이다.

마지막 테스트 케이스 다음 줄에는 $0$ 두 개가 주어진다. 이 줄은 처리하지 않는다.

각 테스트 케이스마다 먼저 Case x: 를 한 줄에 출력한다. $x$는 $1$부터 시작하는 테스트 케이스 번호이다. 이어서 $N$개의 줄을 출력한다. $i$번째 줄에는 노드 $i$를 루트로 삼았을 때의 최소 배치 비용을 출력한다.