B. Назначение весов ребрам
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У вас есть невзвешенное дерево на $$$n$$$ вершинах. Вы должны назначить положительный вес каждому ребру, чтобы выполнялось следующее условие:

  • Для каждых двух разных листов $$$v_{1}$$$ и $$$v_{2}$$$ этого дерева, побитовое исключающее ИЛИ весов всех ребер на простом пути между $$$v_{1}$$$ и $$$v_{2}$$$ должно быть равно $$$0$$$.

Обратите внимание, что вы можете назначать очень большие натуральные числа (такие как $$$10^{(10^{10})}$$$).

Гарантируется, что такое назначение всегда существует при данных ограничениях. Теперь определим $$$f$$$ как количество различных весов среди назначенных весов.

В этом примере назначение верно, потому что побитовое исключающее ИЛИ всех весов ребер между каждой парой листьев равно $$$0$$$. Значение $$$f$$$ здесь равно $$$2$$$, потому что есть $$$2$$$ различных веса ребер ($$$4$$$ и $$$5$$$).

В этом примере назначение не удовлетворяет условию, поскольку побитовое исключающее ИЛИ всех весов ребер между вершинами $$$1$$$ и $$$6$$$ ($$$3, 4, 5, 4$$$) не равно $$$0$$$.

Чему равны минимальное и максимальное возможные значения $$$f$$$ для данного дерева? Найдите и выведите оба.

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

Первая строка содержит целое число $$$n$$$ ($$$3 \le n \le 10^{5}$$$)  — количество вершин в данном дереве.

$$$i$$$-я из следующих $$$n-1$$$ строк содержит два целых числа $$$a_{i}$$$ и $$$b_{i}$$$ ($$$1 \le a_{i} \lt b_{i} \le n$$$)  — это означает, что существует ребро между $$$a_{i}$$$ и $$$b_{i}$$$. Гарантируется, что данный граф образует дерево из $$$n$$$ вершин.

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

Выведите два целых числа  — минимальное и максимальное возможное значения $$$f$$$, которые могут быть получены из правильного назначения данного дерева. Обратите внимание, что такое назначение всегда существует при данных ограничениях.

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

В первом примере возможные назначения для минимума и максимума показаны на рисунке ниже. Конечно, есть и другие назначения.

Во втором примере возможные назначения для минимума и максимума показаны на рисунке ниже. Значение $$$f$$$ для правильного назначения этого дерева всегда равно $$$3$$$.

В третьем примере возможные назначения для минимума и максимума показаны на рисунке ниже. Конечно, есть и другие назначения.