Problem D
Raktuvjtrīce

Veiksmes raktuve, Eja, Ashley Dace. License CC BY-SA 2.0.

Pilnīgi autonomās alus mikrodarītavas, kas uzstādītas pamestajās Moravijas rūķu raktuvēs, patiesi ir pierādījums rūķu atjautībai un meistarībai! Diemžēl dažreiz raktuves tiek satricinātas ar zemestrīcēm, kas izraisa cauruļvadu un piltuvju novirzes, kā rezultātā dārgais dzēriens izlīst uz grīdas. Kā Cildenam Alus Darītavas Drošības Uzraugam, jūsu pienākums izslēgt ierīces visās zālēs, ja notiek zemestrīce.

Tuneļu caurstaigāšana aizņem laiku, tāpēc jūs neizbēgami ieradīsīties pie daudzām ierīcēm ar nokavēšanos. No tā nevar izvairīties, bet jūs vēlaties minimizēt kopējo izlijušā dzēriena daudzumu.

Rūķu raktuves sastāv no $n$ zālēm, kas savienotas ar $n-1$ tuneļiem. Visa sistēma ir savienota, tāpēc ir iespējams nokļūt no jebkuras zāles līdz jebkurai citai. Viena tuneļa caurstaigāšana aizņem $1$ laika vienību. Ierīču izslēgšana un zāles caurceļošana neprasa laiku. Ja zālē ierīces tiek atslēgtas laikā $t$ pēc zemestrīces, tas izraisīs $t$ litrus izlijušā dzēriena tajā zālē. Ir tieši viena zemestrīce, kas skar visas zāles vienlaicīgi, un jūs nevarat izslēgt nevienu ierīci pirms zemestrīces. Jūs varat sākt jebkurā no zālēm.

Piemērs

$1$. piemērā raktuves izskatīsies šādi:

Ja sākt $2$. zālē un apmeklēt pārējās zāles secībā $2$., $1$., $2$., $3$., tad var izslēgt ierīces tajās laikā $0$ ($2$. zālē), laikā $1$ ($1$. zālē) un laikā $3$ ($3$. zālē). Tas kopumā izšķiež $0+1+3=4$ litrus dzēriena. Ja sākt $1$. zālē un apmeklēt zāles secībā $1$., $2$., $3$., tad kopējais izšķērdētā dzēriena daudzums būs $0+1+2=3$ litri, kas ir labāk.

Ievaddati

Ievada pirmā rinda satur veselu skaitli $n$, kas apzīmē zāļu skaitu. Tiek pieņemts, ka zāles tiek numurētas ar skaitļiem $1$, $\dots$, $n$. Nākāmās $n-1$ rindas katra satur divus ar atstarpi atdalītus veselus skaitļus $u$ un $v$ ar $1\le u<v\le n$, kas nozīmē, ka zāles $u$ un $v$ ir savienotas ar tuneli.

Izvaddati

Izvadiet vienu veselu skaitli, vismazāko iespējamo izlītā dzēriena daudzumu litros.

Ierobežojumi un vērtēšana

Vienmēr izpildās ierobežojums $1\le n\le {10}^5$.

Jūsu risinājums tiks pārbaudīts uz vairākām testu grupām. Katra grupa ir vērta noteiktu punktu skaitu. Katra testu grupa satur vairākus testus. Lai saņemtu punktus par testu grupu, ir jāatrisina visi testi testu grupā. Jūsu gala rezultāts būs lielākais punktu skaits, kas iegūts ar vienu risinājuma iesniegumu.

3
1 2
2 3

3

4
1 2
1 3
1 4

7

1

0