У вас есть дерево из \(n\) вершин. Вы собираетесь преобразовать это дерево в \(n\) резинок на бесконечной плоскости. Должно выполняться следующее;
Теперь давайте дадим следующие определения:
Можно доказать, что при заданных ограничениях существует преобразование и последовательность вложенных резинок.
Какую максимальную длину последовательности вложенных резинок можно получить из данного дерева? Найдите и выведите ее.
Первая строка содержит целое число \(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\) вершин.
Выведите ответ.
В первом примере можно получить вложенную последовательность из \(4\) резинок (\(1\), \(2\), \(5\) и \(6\)) с помощью следующего преобразования, приведенного ниже. Конечно, существуют и другие преобразования для создания вложенной последовательности длины \(4\). Однако вы не можете сделать последовательность из \(5\) или более вложенных резинок для данного дерева.
Одно из возможных преобразований для второго примера приведено ниже.
6 1 3 2 3 3 4 4 5 4 6
4
4 1 2 2 3 3 4
2
1000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач