Задачи
Поезда Хобсона
Поезда Хобсона
Г-н Хобсон ушел из управления конюшней и вложил средства в более современный вид транспорта --- поезда. Он построил железнодорожную сеть из $n$ станций. Однако он сохранил свою приверженность к освобождению пассажира от бремени слишком большого выбора: с каждой станции пассажир может сесть на поезд ровно до одной другой станции. Такое путешествие называется \textbf{этап}. Обратите внимание, что это путешествие в один конец, и вернуться обратно может не быть возможности.
Хобсон также предлагает ровно один вариант билета, который позволяет пассажиру проехать до $k$ этапов за одну поездку. На выходе с каждой станции стоит автоматизированный считыватель билетов (только один, чтобы пассажирам не приходилось решать, каким воспользоваться). Автомат проверяет, что расстояние от начальной станции до конечной не превышает $k$ этапов.
Каждый считыватель билетов должен быть запрограммирован списком допустимых стартовых станций. Однако чем больше памяти потребуется для этого списка, тем дороже будет машина. Помогите Хобсону, определив для каждой станции $A$ количество станций (включая $A$), с которых клиент может добраться до $A$ не более чем за $k$ этапов.
\includegraphics{https://static.eolymp.com/content/d8/d8o5cl81tl77r9s08ivdtsh65k.gif}
Рисунок H.1: Иллюстрация к примеру 1. Каждый кружок представляет станцию. Числа вне кружков --- это номера станций, загруженные в считыватели билетов при $k = 2$.
\InputFile
В первой строке записаны два целых числа $n$ и $k$, где $n~(2 \le n \le 5 \cdot 10^5)$ --- количество станций, а $k~(1 \le k \le n - 1)$ --- максимальное количество этапов, которое можно проехать по билету. Далее следуют $n$ строк, $i$-я из которых содержит целое число $d_i~(1 \le di \le n$ и $d_i \ne i)$ --- станцию, до которой можно добраться со станции $i$ на одном участке.
\OutputFile
Выведите $n$ строк. В $i$-й строке выведите количество станций, с которых можно добраться до станции $i$ не более чем за $k$ этапов.
Входные данные #1
6 2 2 3 4 5 4 3
Выходные данные #1
1 2 4 5 3 1
Входные данные #2
5 3 2 3 1 5 4
Выходные данные #2
3 3 3 2 2