Розподіл Дерев
Дерева є однією з найпопулярніших структур даних в інформатиці. Хоча дерева мають елегантну структуру, вони не зовсім сумісні з сучасною архітектурою комп'ютерів. У сучасних комп'ютерах пам'ять організована як одномірний масив. Оскільки дерево не є одномірною структурою, це може вплинути на ефективність кешу, коли дерево розміщується в пам'яті. Доступ до даних відбувається швидше, якщо вони вже знаходяться в кеші. Розглянемо, як можна розмістити вузли дерева для досягнення високої продуктивності кешу.
Ми визначаємо вартість розміщення дерева наступним чином. Для простоти припустимо, що пам'ять розділена на блоки, кожен з яких може вмістити не більше B вузлів дерева. Коли ми звертаємося до даних у блоці, всі дані цього блоку зберігаються в кеші, і подальший доступ до даних у цьому блоці буде швидшим. Вартість доступу до вузла u після вузла v дорівнює 0, якщо u і v знаходяться в одному блоці, і 1 в іншому випадку. Спочатку кеш порожній, тому вартість доступу до вузла завжди дорівнює 1. Вартість шляху v_1, v_2, ..., v_n є сумою вартостей, коли ми отримуємо доступ до вузлів v_1, v_2, ..., v_n у цьому порядку. Для дерева ми визначаємо вартість розміщення як максимальну вартість шляхів від кореневого вузла до кожного кінцевого вузла.
Нижченаведені рисунки демонструють приклади розміщення, коли B = 4 і вузол 1 є кореневим вузлом (це відповідає дереву, описаному в третьому прикладі вхідних даних). Кожна рамка представляє блок. Лівий рисунок є прикладом розміщення з вартістю 3. Це не оптимально, оскільки правий приклад досягає оптимальної вартості розміщення 2.
Для даного дерева, обчисліть мінімальну вартість розміщення для кожного вузла i, коли цей вузол є кореневим.
Вхідні дані
Вхід містить кілька тестових випадків. Кожен тестовий випадок починається з рядка, що містить два цілі числа N (1 ≤ N ≤ 100000) і B (1 ≤ B ≤ N), розділені пробілом. Кожен з наступних N−1 рядків містить ціле число. i-те число p_i (1 ≤ p_i ≤ i) вказує, що вузол i+1 з'єднаний з вузлом p_i. Вузли пронумеровані від 1 до N.
Останній тестовий випадок супроводжується рядком, що містить два нулі.
Вихідні дані
Для кожного тестового випадку виведіть номер випадку. Потім виведіть N рядків. i-й рядок повинен містити ціле число, яке позначає мінімальну вартість розміщення даного дерева, коли вузол i є кореневим.
Дотримуйтесь формату зразкового виводу.