Две голодные красные панды, Оскар и Лура, получили в подарок дерево \(T\) с \(n\) вершинами. Они хотят выполнить следующую процедуру перемешивания для всего дерева \(T\) ровно один раз. С помощью этой процедуры они создадут новое дерево из вершин старого дерева:
- Выбрать любую вершину \(V\) из исходного дерева \(T\). Создать новое дерево \(T_2\) с \(V\) в качестве корня.
- Удалить \(V\) из \(T\) так, чтобы исходное дерево было разбито на одно или несколько поддеревьев (или ноль поддеревьев, если \(V\) является единственной вершиной в \(T\)).
- Перемешать каждое поддерево с помощью той же процедуры (снова выбирая любую вершину в качестве корня), затем соединить корни всех перетасованных поддеревьев с \(V\), чтобы закончить построение \(T_2\).
После этого у Оскара и Луры остается новое дерево \(T_2\). Они могут есть только листья и очень голодны. Поэтому они просят вас помочь им найти максимальное количество листьев среди всех деревьев, которое можно получить за ровно одно перемешивание.
Обратите внимание, что листья — это все вершины со степенью \(1\). Таким образом, корень может считаться листом, если у него есть только один ребенок.
Выходные данные
Для каждого набора входных данных выведите одно целое число — максимальное количество листьев, достижимое с помощью одной операции.
Примечание
В первом наборе входных данных можно показать, что максимальное количество листьев равно \(4\). Для этого мы можем начать перемешивание с выбора вершины \(3\) в качестве нового корня.
Далее у нас остается только одно поддерево, в котором мы можем выбрать вершину
\(2\) в качестве нового корня этого поддерева.
Это заставит все оставшиеся
\(3\) вершины стать листьями, и когда мы присоединим их обратно к нашему новому корню, перемешанное поддерево будет выглядеть так:
Мы соединяем перемешанное поддерево обратно с корнем нашего нового дерева. Наше конечное дерево имеет четыре листа (включая корень) и выглядит следующим образом:
Во втором наборе входных данных у нас есть бамбук из пяти вершин. Можно показать, что максимальное количество листьев после одного перемешивания составляет \(3\). Мы можем начать с вершины \(2\), которая заставит вершину \(1\) стать листом. Затем, если мы выберем вершину \(4\) с правой стороны, вершины \(3\) и \(5\) также окажутся листьями.
Третий набор входных данных представляет собой граф-звезду с шестью вершинами. Количество листьев не может увеличиться, поэтому наш ответ будет равен \(5\) (если мы начнем перемешивание с исходной корневой вершины).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
5
1 2
1 3
2 4
2 5
5
1 2
2 3
3 4
4 5
6
1 2
1 3
1 4
1 5
1 6
10
9 3
8 1
10 6
8 5
7 8
4 6
1 3
10 1
2 7
|
4
3
5
6
|