Hobson's Trains

Mr. Hobson has retired from running a stable and invested in a more modern form of transport, trains. He built a rail network with $n$ stations. He still wants to spare passengers from too many choices: from each station, a passenger can catch a train to exactly one other station. Such a trip is called a leg. Trips are one-way, so a passenger may not be able to return.

Hobson also sells exactly one type of ticket, which lets a passenger travel up to $k$ legs in one trip. Each station has one automated ticket reader at its exit (only one, so passengers do not need to decide which to use). The reader checks that the distance from the starting station to the final station does not exceed $k$ legs.

Each reader must be programmed with a list of valid starting stations. The longer the list, the more expensive the machine. For each station $A$, count the stations (including $A$ itself) from which a customer can reach $A$ in at most $k$ legs.

Figure H.1: Sample Input 1 with $k = 2$. Each circle is a station. The numbers outside the circles are the station numbers loaded into the ticket readers when $k = 2$.

The first line contains two integers $n$ and $k$, where $2 \le n \le 5 \cdot 10^5$ is the number of stations and $1 \le k \le n - 1$ is the maximum number of legs that may be traveled on a ticket. Then $n$ lines follow. The $i$-th of them contains an integer $d_i$ ($1 \le d_i \le n$, $d_i \ne i$), the station that can be reached from station $i$ in one leg.

Output $n$ lines. The $i$-th line contains the number of stations from which station $i$ can be reached in at most $k$ legs.