Problem D
Minequake

Goodluck Mine, Passage autorstwa Ashley Dace. Licencja CC BY-SA 2.0.

W pełni autonomiczne mikrobrowary zainstalowane w opuszczonych krasnoludzkich kopalniach na Morawach są prawdziwym świadectwem pomysłowości i kunsztu krasnoludzkiej inżynierii! Niestety, czasami trzęsienia ziemi wstrząsają kopalniami, co prowadzi do nieprawidłowego ustawienia rur i lejków, które rozlewają cenny płyn na podłogę. Jako Najwyższy Strażnik Bezpieczeństwa Browaru masz obowiązek wyłączyć maszyny w każdej hali gdy nastąpi trzęsienie ziemi.

Chodzenie po tunelach wymaga czasu, więc nieuchronnie spóźnisz się do wielu maszyn. Nie da się tego uniknąć, ale chcesz zminimalizować całkowitą ilość rozlanego płynu.

Kopalnie Krasnoludów składają się z $n$ hal połączonych $n-1$ tunelami. Cały system jest spójny, więc możliwe jest dostanie się z każdej hali do każdej innej. Przemierzenie tunelu zajmuje $1$ jednostkę czasu. Wyłączenie maszyn i przemierzenie hali nie zajmuje żadnego czasu. W każdej hali wyłączenie maszyn w czasie $t$ po trzęsieniu ziemi powoduje rozlanie $t$ litrów cieczy. Jest dokładnie jedno trzęsienie ziemi, które dotyka wszystkie hale jednocześnie i nie możesz wyłączyć żadnych maszyn ściśle przed trzęsieniem ziemi. Możesz zacząć w dowolnej z hal.

Przykład

W przykładowym wejściu $1$, kopalnie wyglądają następująco:

Jeśli zaczynasz w hali $2$ i odwiedzasz pozostałe hale w kolejności $2$, $1$, $2$, $3$, to możesz wyłączyć ich maszyny w czasie $0$ (w hali $2$), czasie $1$ (w hali $1$) oraz czasie $3$ (w hali $3$). W ten sposób marnuje się łącznie $0+1+3=4$ litrów płynu. Jeśli zamiast tego zaczniesz w hali $1$ i odwiedzisz hale w kolejności $1$, $2$, $3$, całkowita ilość zmarnowanego płynu wynosi $0+1+2=3$ litrów, co jest lepsze.

Wejście

W pierwszym wierszu wejścia znajduje się liczba całkowita $n$, oznaczająca liczbę hal. Zakładamy, że hale są ponumerowane $1$, $\ldots $, $n$. W kolejnych $n-1$ wierszach znajdują się po dwie oddzielone spacjami liczby całkowite $u$ oraz $v$ spełniające $1\leq u < v \leq n$, oznaczające, że istnieje tunel między halą $u$ oraz halą $v$.

Wyjście

Wypisz jedną liczbę całkowitą: minimalną ilość rozlanego płynu, w litrach.

Ograniczenia i punktacja

Zawsze jest spełnione $1\leq n\leq 10^5$.

Twoje rozwiązanie zostanie przetestowane na zestawie grup testowych, z których każda warta jest pewną liczbę punktów. Każda grupa testowa zawiera zestaw przypadków testowych. Aby uzyskać punkty za grupę testową musisz rozwiązać wszystkie przypadki testowe w tej grupie. Twój ostateczny wynik będzie maksymalnym wynikiem pojedynczego zgłoszenia.

3
1 2
2 3

3

4
1 2
1 3
1 4

7

1

0