Погоня за метеликом

У ясні літні дні Нюша любить ловити метеликів на свіжому повітрі. Але сьогодні їй потрапив особливо хитрий метелик: він залетів у лабіринт і спробував сховатися там від Нюші.

Лабіринт складається з $n$ кімнат, пронумерованих від $1$ до $n$, деякі з яких з'єднані коридорами. Відомо, що між будь-якими двома кімнатами існує єдиний шлях, що проходить тільки через коридори. Іншими словами, лабіринт є деревом, що складається з $n$ вершин і n - 1 ребер.

Вхід до лабіринту знаходиться в кімнаті з номером $1$. Листом називається будь-яка кімната, з'єднана рівно з однією іншою кімнатою і яка не збігається з коренем (кімнатою номер $1$). У кожному листі розташований вихід з лабіринту. Метелик починає свій політ з кімнати номер $1$ в напрямку одного з виходів. Він рухається з постійною швидкістю, не розвертається, і щохвилини пролітає один коридор, переходячи в сусідню кімнату. Всі коридори мають однакову довжину.

Щоб зловити метелика, Нюша вирішила покликати на допомогу кілька друзів. Спочатку кожен з них може зайняти будь-яку з кімнат з виходом. Як тільки метелик почне рух від входу до якогось виходу, друзі можуть одразу ж почати рухатися зі своїх кімнат у напрямку до входу. Вони рухаються з тією ж швидкістю, що і метелик. Якщо хтось із них зустріне метелика — будь то в кімнаті чи посеред коридору — він вважається спійманим. Якщо ж метелик добереться до виходу, не стикнувшись із жодним з друзів, він благополучно вибереться на волю.

Допоможіть Нюші визначити мінімальну кількість друзів, необхідних для того, щоб гарантовано спіймати метелика, незалежно від того, до якого виходу він полетить.