Задача 5. Оптимальное удаление ≡

Условие

Дано дерево, состоящее из n вершин. Корнем дерева считается вершина под номером 1. Необходимо удалить одно ребро из дерева (образовав тем самым еще одно дерево с новым корнем) так, чтобы сумма расстояний от корня до всех вершин была минимально возможной. Напишите программу, которая определит эту сумму.

Формат входных данных

В первой строке записано целое число n - количество вершин в дереве.

В следующих n − 1 строках записано по два различных целых числа a_i и b_i - вершины дерева, которые соединены между собой.

Формат выходных данных

Выведите одно целое число - минимально возможную сумму расстояний от корня до всех вершин.

Ограничения

2 ≤ n ≤ 10⁵

1 ≤ a_i, b_i ≤ n

Система оценки и описание подзадач

Баллы за подзадачи начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.

Пояснение к примеру

Минимальную сумму расстояний от корня до всех вершин можно получить, удалив ребро между вершинами 4 и 9. Тогда сумма расстояний от корня до всех вершин первого дерева будет 14, а второго (с корнем в вершине 9) 1.

Примеры тестов

10
1 2
1 3
2 4
2 5
3 6
4 9
6 7
6 8
9 10

15