Корова в небезпеці (Золото)

Зрештою загнана в кут, Бессі причаїлася на віддаленій фермі. Ферма складається з $n$ корівників та n - 1 двосторонніх тунелів між ними, причому між будь-якою парою корівників існує єдиний шлях. Кожен корівник, з якого веде лише один тунель, є виходом. Коли настане ранок, Бессі з'явиться на поверхні в одному з корівників і спробує дістатися до виходу.

Проте щойно Бессі вийде на поверхню, стражі порядку зможуть точно визначити її місцезнаходження. Тоді кілька фермерів почнуть рух з різних корівників-виходів і спробують спіймати Бессі. Фермери рухаються з тією ж швидкістю, що й Бессі, тобто за кожну одиницю часу кожен фермер може перейти з одного корівника до сусіднього. Фермери в будь-який момент знають, де знаходиться Бессі, а Бессі в будь-який момент знає, де знаходяться фермери. Фермери ловлять Бессі, якщо в якийсь момент один із фермерів перебуває в тому ж корівнику, що й Бессі, або проходить тим самим тунелем, що й вона. Навпаки, Бессі рятується, якщо вона дістанеться до корівника-виходу раніше, ніж її спіймає якийсь фермер.

Бессі не впевнена у своїх шансах на успіх, адже вони залежать від того, скількох фермерів зможуть задіяти стражі порядку. Відомо, що Бессі вийде на поверхню в корівнику $k$. Допоможіть їй визначити мінімальну кількість фермерів, необхідну, щоб її спіймати, за умови, що фермери оптимально розподіляться по корівниках-виходах.