Демиурги Шамбамбукли и Мазукта любят наблюдать за играми обычных людей. Сегодня они заметили двух людей, которые играют в следующую игру.

Дано корневое дерево на n вершинах, m из которых являются листьями (лист — это такая вершина, у которой нет ни одного ребенка), ребра дерева ориентированы по направлению от родителя к детям. В листьях дерева расставлены целые числа от 1 до m таким образом, что каждое число встречается ровно в одном листе.

Изначально в корень дерева помещается фишка. Оба игрока ходят по очереди, на своем ходу игрок перемещает фишку из текущей вершины в одного из ее детей; если игрок не может сделать ход, игра немедленно заканчивается. Результатом игры является число, записанное в листе, в котором фишка завершила свое движение. Игрок, совершающий первый ход, стремится максимизировать результат игры, а второй игрок, наоборот, стремится минимизировать результат. Можно предполагать, что оба игрока действуют оптимально.

Демиурги всемогущи, поэтому они могут до начала игры произвольным образом переставить числа, записанные в листьях. Шамбамбукли хочет расставить числа таким образом, чтобы результат игры при оптимальной игре обоих игроков был как можно больше, а Мазукта хочет, чтобы результат был как можно меньше. Каким будет результат игры, если числа расставит Шамбамбукли, а каким, если числа расставит Мазукта? Разумеется, демиурги выбирают наилучший для себя вариант расстановки чисел.