Убить всех термитов

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

1

1

2
1

1

8
1 1 2 1 2 3 2

2