- Time limit: 4.00 s
- Memory limit: 128 MB
Uolevi ja Maija olivat kauan ystävät, mutta sitten heille tuli riita. Tehtäväsi on valita heille uudet asuinpaikat niin, että he asuvat mahdollisimman kaukana toisistaan.
Sinulle on annettu tiedot kaupungeista ja niiden välisistä teistä. Kaikkien kaupunkien välillä on olemassa reitti, ja teitä on tasan yksi vähemmän kuin kaupunkeja.
Syöte
Syötteen ensimmäisellä rivillä on kokonaisluku n: kaupunkien määrä. Kaupungit on numeroitu kokonaisluvuin 1,2,\ldots,n.
Tämän jälkeen syötteessä on n-1 riviä, joista jokainen kuvaa yhden tien. Rivillä on kaksi kokonaislukua a ja b: mistä kaupungista tie alkaa ja mihin se päättyy. Kaikki tiet ovat kaksisuuntaisia.
Tuloste
Ohjelmasi tulee tulostaa yksi kokonaisluku: teiden määrä Uolevin ja Maijan välillä, kun he asettuvat asumaan mahdollisimman kaukana toisistaan oleviin kaupunkeihin.
Rajat
- 2\leq n\leq 5\cdot 10^4
Esimerkki
Syöte:
5 1 2 1 3 3 4 3 5
Tuloste:
3
Selitys: Uolevi muuttaa kaupunkiin 2 ja Maija muuttaa kaupunkiin 4. Nyt heidän välillään on 3 tietä.