Problem K
Kaivosjäristys

Goodluck Mine, Passage. Kuvannut Ashley Dace. Lisenssi CC BY-SA 2.0.

Moravian hylättyihin kääpiökaivoksiin asennetut täysin itsenäiset pienpanimot ovat todellinen osoitus kääpiöiden insinööritaidon nerokkuudesta ja taitavuudesta! Valitettavasti maanjäristykset toisinaan ravistelevat kaivoksia, jolloin putket ja suppilot vahingoittuvat ja kallisarvoista nestettä valuu lattialle. Maanjäristyksen sattuessa on sinun velvollisuutesi Panimoturvallisuuden Ylhäisenä Vartijana sammuttaa jokaisen salin kone.

Tunneleissa kulkeminen vie aikaa, joten tulet väistämättä myöhässä monien koneiden luo. Tätä ei voida välttää, mutta haluat minimoida vuotaneen nesteen kokonaismäärän.

Kääpiökaivos koostuu $n$:stä salista, joita yhdistää $n-1$ tunnelia. Kaivos on yhtenäinen, eli jokaisesta salista pääsee mihin tahansa toiseen saliin. Yhden tunnelin läpi kulkeminen vie yhden aikayksikön. Koneiden sammuttaminen ja salien läpi kulkeminen ei vie aikaa. Jos koneen sammuttaa ajanhetkellä $t$ järityksen alusta, $t$ litraa nestettä on ehtinyt mennä hukkaan. Järistyksiä on täsmälleen yksi, ja se vaikuttaa jokaiseen saliin samanaikaisesti. Koneita ei saa sammuttaa ennen järistyksen alkua. Voit lähteä liikkeelle mistä tahansa salista.

Esimerkki

Esimerkin $1$ kaivos näyttää tältä:

Jos aloitat salista $2$ ja kuljet loput saleista järjestyksessä $2$, $1$, $2$, $3$, voit sammuttaa koneet ajanhetkillä $0$ (salissa $2$), $1$ (salissa $1$) ja $3$ (salissa $3$). Tällöin menee hukkaan yhteensä $0+1+3=4$ litraa nestettä. Jos sen sijaan aloitat salista $1$ ja kuljet salit järjestyksessä $1$, $2$, $3$, nestettä menee hukkaan yhteensä vain $0+1+2=3$ litraa, mikä on parempi.

Syöte

Syötteen ensimmäisellä rivillä on yksi kokonaisluku $n$, salien määrä. Hallit on numeroitu luvuilla $1$, $\ldots $, $n$. Jokainen seuraavista $n-1$ rivistä sisältää kaksi välilyönnillä erotettua kokonaislukua $u$ ja $v$, joille pätee $1\leq u < v \leq n$, tarkoittaen, että salien $u$ ja $v$ välillä on tunneli.

Tuloste

Tulosta yksi kokonaisluku: pienin mahdollinen litramäärä hukkaan mennyttä nestettä.

Rajoitukset ja pisteytys

Kaikille syötteille pätee $1\leq n\leq 10^5$.

Ratkaisu testataan testiryhmillä, joista kullakin on oma pistemäärä. Jokainen testiryhmä sisältää joukon testitapauksia. Ryhmän pisteet saa vain, jos ratkaisee kaikki sen testitapaukset. Tehtävän lopullinen pistemäärä on suurin yksittäisen lähetyksen pistemäärä.

3
1 2
2 3

3

4
1 2
1 3
1 4

7

1

0