Корова в небезпеці (Платина)
Загнана в кут, Бессі вирушила на далеку ферму. Ферма складається з n сараїв і n - 1 двонаправлених тунелів, так що між кожною парою сараїв існує унікальний шлях. Кожен сарай, що має лише один тунель, є виходом. Коли настане ранок, Бессі з'явиться в якомусь сараї і спробує дістатися до виходу.
Однак, як тільки Бессі з'явиться на поверхні, представники закону зможуть визначити її місцезнаходження. Після цього деякі фермери спробують зловити Бессі біля різних виходів. Фермери рухаються з тією ж швидкістю, що й Бессі (тобто на кожному кроці кожен фермер може переміщатися з одного сараю в сусідній). Фермери завжди знають, де знаходиться Бессі, а Бессі завжди знає, де знаходяться фермери. Фермери зловлять Бессі, якщо в якийсь момент фермер опиниться в тому ж сараї, що й Бессі, або перетне той самий тунель, що й вона. І навпаки, Бессі втече, якщо досягне виходу раніше, ніж її зловлять фермери.
Бессі не впевнена, в якому сараї їй слід з'явитися. Для кожного з n сараїв допоможіть Бессі визначити мінімальну кількість фермерів, яка знадобиться, щоб зловити її, якщо вона з'явиться там, припускаючи, що фермери оптимально розподіляться між виходами.
Вхідні дані
Перша стрічка містить n (2 ≤ n ≤ 7 * 10^4). Кожна з наступних n - 1 стрічок містить два цілих числа, кожне в діапазоні від 1 до n, що описують тунель між двома сараями.
Вихідні дані
Виведіть n рядків, де i-ий рядок містить мінімальну кількість фермерів, необхідну для поимки Бессі, якщо вона з'явиться в i-му сараї.