E. Демиурги играют снова
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

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

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

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

Входные данные

В первой строке записано одно целое число n — количество вершин в дереве (1 ≤ n ≤ 2·105).

В следующих n - 1 строках записано по два целых числа ui и vi (1 ≤ ui, vi ≤ n) — концы очередного ребра дерева; ребро ведет из вершины ui в вершину vi. Гарантируется, что описанный граф является корневым деревом, корень дерева находится в вершине 1.

Выходные данные

Выведите два целых числа через пробел — максимально возможный и минимально возможный результат игры.

Примеры
Входные данные
5
1 2
1 3
2 4
2 5
Выходные данные
3 2
Входные данные
6
1 2
1 3
3 4
1 5
5 6
Выходные данные
3 3
Примечание

Разберем первый пример. В дереве три листа: 3, 4 и 5. Если в вершину 3 поместить максимальное число 3, первый игрок своим ходом пойдет туда и результат будет равен 3. С другой стороны, легко видеть, что при любой расстановке первый игрок может гарантировать результат не менее 2.

Во втором примере независимо от расстановки первый игрок может пойти по тому из трех путей, который заканчивается листом с числом 3.