Корова в небезпеці (Платина)#10427
Загнана нарешті в кут, Бессі сховалася на віддаленій фермі. Ферма складається з амбарів і n - 1 двобічних тунелів між ними, причому між будь-якою парою амбарів існує єдиний шлях. Кожен амбар, з якого веде лише один тунель, є виходом. Коли настане ранок, Бессі вийде на поверхню в одному з амбарів і спробує дістатися виходу.
Проте щойно Бессі вийде на поверхню в якомусь амбарі, правоохоронці зможуть точно визначити її місцеперебування. Тоді кілька фермерів почнуть рух із різних амбарів-виходів і спробують упіймати Бессі. Фермери рухаються з тією самою швидкістю, що й Бессі, тобто за кожну одиницю часу кожен фермер може перейти з одного амбара до сусіднього. Фермери в будь-який момент знають, де перебуває Бессі, а Бессі в будь-який момент знає, де перебувають фермери. Фермери ловлять Бессі, якщо в якийсь момент один із фермерів перебуває в тому самому амбарі, що й Бессі, або проходить тим самим тунелем, що й вона. Навпаки, Бессі рятується, якщо дістанеться амбара-виходу строго раніше, ніж її впіймає будь-який фермер.
Бессі не знає, в якому амбарі їй варто вийти на поверхню. Для кожного з амбарів допоможіть їй визначити мінімальну кількість фермерів, потрібну, щоб її впіймати, якщо вона вийде на поверхню саме там, за умови, що фермери оптимально розподіляться по амбарах-виходах.
Перший рядок містить ціле число n~(2 \le n \le 7 \cdot 10^4). Кожен із наступних n - 1 рядків містить два цілих числа a_i і b_i~(1 \le a_i, b_i \le n), що описують тунель між амбарами a_i і b_i.
Виведіть рядків. У -му рядку має міститися мінімальна кількість фермерів, потрібна, щоб упіймати Бессі, якщо вона вийде на поверхню в амбарі .
Приклад 1