D. Укрась яблоню
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В саду Аркадия растет одна яблоня. Ее можно представить как множество точек развилок, соединенных ветками так, что между любыми двумя развилками существует ровно один путь по веткам. Развилки пронумерованы от $$$1$$$ до $$$n$$$, развилка номер $$$1$$$ называется корнем.

Поддеревом развилки $$$v$$$ называется множество развилок $$$u$$$ таких, что путь из $$$u$$$ в корень проходит через $$$v$$$. Обратите внимание, сама вершина $$$v$$$ тоже входит в поддерево $$$v$$$.

Листом называется такая развилка, поддерево которой содержит только одну развилку.

Скоро Новый год, поэтому Аркадий решил украсить яблоню. Он повесит по лампочке некоторого цвета на каждый лист и затем посчитает число счастливых развилок. Счастливой развилкой называется такая развилка $$$t$$$, что все лампочки в поддереве $$$t$$$ имеют различные цвета.

Аркадий заинтересован в следующем вопросе: для каждого $$$k$$$ от $$$1$$$ до $$$n$$$, какое минимальное число различных цветов лампочек необходимо, чтобы число счастливых развилок было не меньше $$$k$$$?

Входные данные

Первая строка содержит одно целое число $$$n$$$ ($$$1 \le n \le 10^5$$$) — количество развилок в дереве.

Вторая строка содержит $$$n - 1$$$ целое число $$$p_2$$$, $$$p_3$$$, ..., $$$p_n$$$ ($$$1 \le p_i < i$$$), где $$$p_i$$$ означает, что есть ветка между развилками $$$i$$$ и $$$p_i$$$. Гарантируется, что данное множество веток задает дерево.

Выходные данные

Выведите $$$n$$$ целых чисел. $$$i$$$-е из них должно быть равно минимальному количеству цветов, необходимых для того, чтобы число счастливых развилок было не меньше $$$i$$$.

Примеры
Входные данные
3
1 1
Выходные данные
1 1 2
Входные данные
5
1 1 3 3
Выходные данные
1 1 1 2 3
Примечание

В первом примере для $$$k = 1$$$ и $$$k = 2$$$ можно все лампочки сделать одного цвета: счастливыми будут развилки $$$2$$$ и $$$3$$$. Для $$$k = 3$$$ нужно повесить лампочки разных цветов, тогда все развилки будут счастливыми.

Во втором примере для $$$k = 4$$$ можно, например, повесить лампочки цвета $$$1$$$ в развилки $$$2$$$ и $$$4$$$, а лампочку цвета $$$2$$$ в развилку $$$5$$$. Тогда счастливыми будут развилки $$$2$$$, $$$3$$$, $$$4$$$ и $$$5$$$.