Погоня за бабочкой

Ясными летними днями Нюша любит ловить бабочек на свежем воздухе. Сегодня ей попалась хитрая бабочка: она залетела в лабиринт и хотела скрыться в нем от Нюши.

Лабиринт состоит из n комнат, пронумерованных от 1 до n, некоторые из которых соединены между собой коридорами. Известно, что между любыми двумя комнатами существует единственный путь из коридоров. Иными словами, лабиринт представляет собой дерево, и количество коридоров равно n - 1.

Вход в лабиринт расположен в комнате с номером 1. Будем называть листом любую комнату лабиринта, которая соединена коридором ровно с одной другой комнатой и не совпадает при этом с корнем. В каждом из листов располагается выход из лабиринта. Бабочка летит от входа по направлению к одному из листов. Она летит с постоянной скоростью и не разворачивается. Все коридоры имеют одинаковую длину, и за одну минуту бабочка пролетает один коридор, перемещаясь в соседнюю комнату.

Для поимки бабочки Нюша решила позвать несколько своих друзей. Исходно каждый из друзей может расположиться в любой из комнат, содержащих выход. В тот момент, когда бабочка начнет лететь от входа в лабиринт к одному из выходов, каждый из друзей может начать двигаться из своей комнаты по направлению ко входу. Друзья двигаются с такой же скоростью, что и бабочка. Если кто-то из друзей оказался в одной точке (в комнате или в середине одного из коридоров) с бабочкой, то бабочка считается пойманной. Если же бабочка долетит до вершины с выходом, не встретив никого из друзей по пути, она благополучно выпорхнет из лабиринта и улетит на свободу.

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

3
1 2
1 3

2

4
1 2
2 3
2 4

1