У вас есть невзвешенное дерево на \(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\) для данного дерева? Найдите и выведите оба.
Выходные данные
Выведите два целых числа — минимальное и максимальное возможное значения \(f\), которые могут быть получены из правильного назначения данного дерева. Обратите внимание, что такое назначение всегда существует при данных ограничениях.
Примечание
В первом примере возможные назначения для минимума и максимума показаны на рисунке ниже. Конечно, есть и другие назначения.
Во втором примере возможные назначения для минимума и максимума показаны на рисунке ниже. Значение \(f\) для правильного назначения этого дерева всегда равно \(3\).
В третьем примере возможные назначения для минимума и максимума показаны на рисунке ниже. Конечно, есть и другие назначения.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
1 3
2 3
3 4
4 5
5 6
|
1 4
|
|
2
|
6
1 3
2 3
3 4
4 5
4 6
|
3 3
|
|
3
|
7
1 2
2 7
3 4
4 7
5 6
6 7
|
1 6
|