Hobson의 기차

Hobson 씨는 마구간 운영에서 은퇴하고, 더 현대적인 교통수단인 기차에 투자했다. 그는 $n$개의 역으로 이루어진 철도망을 건설했다. 다만 승객이 선택지에 너무 시달리지 않도록 하겠다는 방침은 그대로 유지했다. 각 역에서 승객은 다른 역 중 정확히 한 곳으로 가는 기차를 탈 수 있다. 이런 이동 한 번을 구간(leg)이라고 한다. 이동은 단방향이라서 되돌아오지 못할 수도 있다.

Hobson 씨는 승차권도 한 종류만 판매하며, 이 승차권으로 한 번의 여정에서 최대 $k$ 구간까지 이동할 수 있다. 각 역의 출구에는 자동 승차권 판독기가 하나씩 있다(승객이 어느 판독기를 쓸지 고를 필요가 없도록 하나만 둔다). 판독기는 출발 역에서 도착 역까지의 거리가 $k$ 구간을 넘지 않는지 확인한다.

각 판독기에는 유효한 출발 역의 목록을 저장해야 한다. 목록이 길수록 기계 가격이 비싸진다. 각 역 $A$에 대해, 최대 $k$ 구간 안에 $A$에 도착할 수 있는 역의 개수($A$ 자신을 포함)를 구하라.

그림 H.1: $k = 2$일 때의 입력 1. 각 원은 역을 나타낸다. 원 밖의 숫자는 $k = 2$일 때 판독기에 입력되는 역 번호이다.

첫 줄에 두 정수 $n$과 $k$가 주어진다. $n$($2 \le n \le 5 \cdot 10^5$)은 역의 개수이고, $k$($1 \le k \le n - 1$)는 승차권으로 이동할 수 있는 최대 구간 수이다. 이후 $n$개의 줄이 주어지며, $i$번째 줄에는 역 $i$에서 한 구간으로 도달할 수 있는 역 $d_i$($1 \le d_i \le n$, $d_i \ne i$)가 주어진다.

$n$개의 줄을 출력한다. $i$번째 줄에는 역 $i$에 최대 $k$ 구간 안에 도달할 수 있는 출발 역의 개수를 출력한다.