- Time limit: 1.00 s
- Memory limit: 128 MB
Uolevi ja Maija olivat kauan ystäviä, mutta sitten heille tuli riita. He haluavat muuttaa asumaan kahteen kaupunkiin niin, että kaupunkien etäisyys on mahdollisimman suuri.
Kaupunkeja on , ja niiden välillä on joukko teitä niin, että jokaisen kahden kaupungin välillä on yksikäsitteinen reitti.
Syöte
Syötteen ensimmäisellä rivillä on kokonaisluku : kaupunkien määrä. Kaupungit on numeroitu .
Sitten syötteessä on riviä, jotka kuvaavat tiet. Jokaisella rivillä on kolme kokonaislukua , ja : kaupunkien ja välillä on tie, jonka pituus on . Kaikki tiet ovat kaksisuuntaisia.
Tuloste
Tulosta yksi kokonaisluku: pisin mahdollinen etäisyys kaupunkien välillä.
Rajat
Esimerkki
Syöte:
5 1 2 3 2 3 5 2 4 2 1 5 7
Tuloste:
15