Вы оказались в Закулисье — бесконечном лабиринте пустых комнат с жёлтыми стенами и мерцающими лампами.
Однако в этот раз лабиринт оказался необычным. Всего в нём $$$n$$$ комнат, соединённых $$$n-1$$$ коридорами так, что из любой комнаты можно добраться до любой другой ровно одним способом (другими словами, лабиринт является деревом).
Закулисье нестабильно. Каждую минуту происходит перестройка: комната, из которой выходит наибольшее количество коридоров, исчезает вместе со всеми ведущими в неё коридорами. Если таких комнат несколько, исчезает комната с наименьшим номером.
После исчезновения комнаты лабиринт может распасться на несколько изолированных частей. При этом на следующей минуте перестройка продолжается уже с учётом оставшихся коридоров.
Вам предстоит провести в Закулисье $$$n$$$ минут. Определите, на сколько изолированных частей распадётся лабиринт после каждой перестройки.
В первой строке дано целое число $$$n$$$ — количество комнат ($$$1 \le n \le 10^5$$$).
В следующих $$$n-1$$$ строках даны два целых числа $$$u$$$ и $$$v$$$, означающие, что комнаты $$$u$$$ и $$$v$$$ соединены коридором ($$$1 \le u, v \le n$$$).
Гарантируется, что изначально из любой комнаты можно добраться до любой другой.
Выведите $$$n$$$ целых чисел. $$$i$$$-е число должно обозначать количество изолированных частей лабиринта после $$$i$$$-й перестройки.
81 21 31 44 54 66 76 8
3 5 5 4 3 2 1 0
