Вова и Марина любят играть в игры, а особенно — придумывать к ним свои правила. Недавно они открыли для себя веселую игру «Чапаев», в которой игроки должны сбивать щелчками шашки вражеского цвета с шахматной доски (также эта игра известна под названием
«Щелкунчики»). Вдоволь наигравшись, они решили модифицировать правила, добавив игре математическую сложность.
Теперь они играют в «Чапаева» не на шахматной доске, а на доске в форме дерева! Их дерево состоит из \(N\) вершин. Вершина 1 является корнем дерева, а из каждой из оставшихся вершин проведено ребро в некоторую вершину с меньшим номером — ее непосредственного
предка.
В игре участвуют шашки одного цвета, изначально расположенные в некоторых вершинах дерева. За один ход игрок выбирает некоторую шашку и щелчком отправляет ее к корню по ребрам дерева, сбивая при этом с доски все встреченные на пути шашки. Сама шашка,
по которой производился удар, после попадания в корень дерева также слетает с доски.
Игроки делают ходы по очереди. Проигрывает тот игрок, к ходу которого на доске не остается шашек.
Придуманная ими игра замечательна также тем, что на одной и той же доске можно играть, начиная с разных начальных позиций шашек. Практика показала, что самые интересные партии получаются, если исходно расставить фишки во все вершины, являющиеся потомками
(непосредственными или косвенными) некоторой вершины Root, при этом в саму вершину Root фишка не ставится.
Дети решили сыграть \(N\) партий, перебрав в качестве вершины Root каждую вершину дерева по одному разу. Если у очередной вершины Root нет потомков, и на доске исходно не оказывается ни одной фишки, то игры не происходит, и дети переходят
к следующей расстановке. В каждой партии Марина ходит первой.
Вова интересуется у вас, в скольких партиях Марина сможет одержать победу, если игроки будут действовать оптимально.
Формат выходного файла
Выведите единственное целое число — количество партий, в которых Марина одержит победу.
Комментарий
Разберем тест из условия. Доска для игры показана на рисунках ниже. Дети сыграют четыре партии, выбирая в качестве Root вершины 1, 2, 3 и 5. Если выбрать в качестве
Root любую из трех оставшихся вершин, на доске исходно не окажется ни одной фишки, поэтому игры не произойдет.
Если выбрать в качестве Root вершину 5, фишки будут исходно находиться в вершинах 6 и 7. В такой партии Марина проигрывает: после того, как она сбивает любую из этих двух фишек с доски, Вова сбивает оставшуюся и заканчивает партию.
Если выбрать в качестве Root вершину 2 или 3, у Марины будет возможность выиграть игру за один ход, щелкнув по фишке из вершины 4 (при этом, в случае Root = 2, она по пути также собьет фишку из 3 вершины по правилам игры)
Можно убедиться, что если выбрать в качестве Root вершину 1, у Марины также будет выигрышная стратегия. Для этого первым ходом Марина должна сбить фишку из вершины 2. Пример партии с таким начальным расположением показан ниже.
Таким образом, Марина выигрывает в трех партиях
Система оценивания
Тесты к этой задаче состоят из пяти групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов предыдущих групп.
0. Тест 1. Тест из условия, оценивается в ноль баллов.
1. Тесты 2–17. В тестах этой группы \(N\) ≤ 20. Эта группа оценивается в 20 баллов
2. Тесты 18–38. В тестах этой группы \(N\) ≤ 200. Эта группа оценивается в 20 баллов.
3. Тесты 39–59. В тестах этой группы \(N\) ≤ 5 000. Эта группа оценивается в 20 баллов.
4. В тестах этой группы дополнительные ограничения отсутствуют. Эта группа оценивается в 40 баллов.
