У вас есть невзвешенное дерево на \(n\) вершинах. Вы должны назначить положительный вес каждому ребру, чтобы выполнялось следующее условие:
Обратите внимание, что вы можете назначать очень большие натуральные числа (такие как \(10^{(10^{10})}\)).
Гарантируется, что такое назначение всегда существует при данных ограничениях. Теперь определим \(f\) как количество различных весов среди назначенных весов.
В этом примере назначение не удовлетворяет условию, поскольку побитовое исключающее ИЛИ всех весов ребер между вершинами \(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\), которые могут быть получены из правильного назначения данного дерева. Обратите внимание, что такое назначение всегда существует при данных ограничениях.
В первом примере возможные назначения для минимума и максимума показаны на рисунке ниже. Конечно, есть и другие назначения.
Во втором примере возможные назначения для минимума и максимума показаны на рисунке ниже. Значение \(f\) для правильного назначения этого дерева всегда равно \(3\).
В третьем примере возможные назначения для минимума и максимума показаны на рисунке ниже. Конечно, есть и другие назначения.
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
1000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач