Problem D
Minequake

Goodluck Mine, Passage by Ashley Dace. License CC BY-SA 2.0.

Повністю автономні мікропивоварні, встановлені в залишених копальнях карликів Моравії, дійсно свідчать про винахідливість та майстерність інженерів-карликів! На жаль, іноді землетруси струшують копальні, що призводить до розгойдування труб та воронок, і проливання дорогоцінної рідини на підлогу. Як на Возвеличеного Стража Безпеки Пивоварні, на Вас покладена відповідальність вимикати машини в кожному залі у випадку землетрусу.

Проходження тунелей займає час, тому Ви невідворотно будете запізнюватися до багатьох машин. Цього не можна уникнути, але Ви хочете мінімізувати загальну кількість розливаної рідини.

Копальні карликів складаються з $n$ залів, що з’єднані $n-1$ тунелем. Уся система зв’язана, тому можливо дістатися з будь-якого залу до будь-якого іншого. Тунелі проходять за 1 одиницю часу. Вимикання машин та проходження залів не займає часу. У кожному залі, вимикання машин у час $t$ після землетрусу розливає $t$ літрів рідини. Є тільки один землетрус, який впливає на всі зали одночасно, і Ви не можете вимкнути жодну машину до землетрусу. Ви можете розпочати в будь-якому залі.

Приклад

У прикладі вхідних даних №1 копальні виглядають так:

Якщо Ви розпочнете з зали №2 і відвідаєте інші зали в порядку $2$, $1$, $2$, $3$, то Ви можете вимкнути їхні машини в час $0$ (у залі $2$), час $1$ (у залі $1$) та час $3$ (у залі $3$). Це зіпсує $0+1+3=4$ літрів рідини загалом. Якщо замість цього Ви розпочнете з залу №1 і відвідаєте зали в порядку $1$, $2$, $3$, загальна кількість витраченої рідини становитиме $0+1+2=3$ літри, що краще.

Вхідні дані

Перший рядок вхідних даних містить ціле число $n$, яке позначає кількість залів. Ми припускаємо, що зали позначені числами від $1$ до $n$. Наступні $n-1$ рядків містять по два цілих числа $u$ та $v$ з пробілом між ними, при цьому $1\leq u < v \leq n$, що означає наявність тунелю між залом $u$ та залом $v$.

Вихідні дані

Виведіть одне ціле число: мінімальну кількість пролитої рідини в літрах.

Обмеження та оцінювання

Ми завжди маємо: $1\leq n\leq 10^5$.

Ваше рішення буде перевірено за допомогою набору тестових груп, кожна з яких оцінюється певною кількістю балів. Кожна тестова група містить набір тестових прикладів. Щоб отримати бали за тестову групу, необхідно успішно вирішити всі тестові приклади цієї групи. Оцінка за завдання буде дорівнювати максимальній кількості балів, отриманій за один варіант розв’язку.

3
1 2
2 3

3

4
1 2
1 3
1 4

7

1

0