В саду Аркадия растет одна яблоня. Ее можно представить как множество точек развилок, соединенных ветками так, что между любыми двумя развилками существует ровно один путь по веткам. Развилки пронумерованы от \(1\) до \(n\), развилка номер \(1\) называется корнем.
Поддеревом развилки \(v\) называется множество развилок \(u\) таких, что путь из \(u\) в корень проходит через \(v\). Обратите внимание, сама вершина \(v\) тоже входит в поддерево \(v\).
Листом называется такая развилка, поддерево которой содержит только одну развилку.
Скоро Новый год, поэтому Аркадий решил украсить яблоню. Он повесит по лампочке некоторого цвета на каждый лист и затем посчитает число счастливых развилок. Счастливой развилкой называется такая развилка \(t\), что все лампочки в поддереве \(t\) имеют различные цвета.
Аркадий заинтересован в следующем вопросе: для каждого \(k\) от \(1\) до \(n\), какое минимальное число различных цветов лампочек необходимо, чтобы число счастливых развилок было не меньше \(k\)?
Выходные данные
Выведите \(n\) целых чисел. \(i\)-е из них должно быть равно минимальному количеству цветов, необходимых для того, чтобы число счастливых развилок было не меньше \(i\).
Примечание
В первом примере для \(k = 1\) и \(k = 2\) можно все лампочки сделать одного цвета: счастливыми будут развилки \(2\) и \(3\). Для \(k = 3\) нужно повесить лампочки разных цветов, тогда все развилки будут счастливыми.
Во втором примере для \(k = 4\) можно, например, повесить лампочки цвета \(1\) в развилки \(2\) и \(4\), а лампочку цвета \(2\) в развилку \(5\). Тогда счастливыми будут развилки \(2\), \(3\), \(4\) и \(5\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
1 1
|
1 1 2
|
|
2
|
5
1 1 3 3
|
1 1 1 2 3
|