Рассмотрим игру, в которой участвуют два игрока, Алиса и Боб. У них есть дерево $$$T$$$, все вершины которого изначально окрашены в белый цвет. Алиса и Боб ходят по очереди: сначала Алиса, потом Боб, потом опять Алиса, потом опять Боб, и так далее.

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

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

Счет в игре — количество красных вершин. Алиса стремится максимизировать счет, Боб — минимизировать. Оба игрока играют оптимально.

На этом описание игры завершено, далее следует само условие задачи.

Дано дерево, изначально состоящее из одной вершины $$$1$$$. К нему делается $$$q$$$ запросов; в ходе $$$i$$$-го запроса в дерево добавляется новая вершина, она получает номер $$$(i+1)$$$ и соединяется ребром с вершиной $$$v_i$$$. После каждого запроса необходимо вывести, какой будет счет в игре, если Алиса и Боб играют на текущем дереве.