Вы оказались в Закулисье — бесконечном лабиринте пустых комнат с жёлтыми стенами и мерцающими лампами.

Однако в этот раз лабиринт оказался необычным. Всего в нём $$$n$$$ комнат, соединённых $$$n-1$$$ коридорами так, что из любой комнаты можно добраться до любой другой ровно одним способом (другими словами, лабиринт является деревом).

Закулисье нестабильно. Каждую минуту происходит перестройка: комната, из которой выходит наибольшее количество коридоров, исчезает вместе со всеми ведущими в неё коридорами. Если таких комнат несколько, исчезает комната с наименьшим номером.

После исчезновения комнаты лабиринт может распасться на несколько изолированных частей. При этом на следующей минуте перестройка продолжается уже с учётом оставшихся коридоров.

Вам предстоит провести в Закулисье $$$n$$$ минут. Определите, на сколько изолированных частей распадётся лабиринт после каждой перестройки.