Šeštadieninė informatikos olimpiadininkų mokykla

Kanadiečiai mėgsta ledo ritulį. Po Ledo Taurės finalo visi sporto fanai keliauja namo, keliuose sukeldami didžiules spūstis. Padėkite kanadiečiams parinkti miestą, kuriame organizuojant Ledo Taurės finalą, didžiausios spūstys keliuose, būtų kuo mažesnės.

Valstybę galime įsivaizduoti kaip jungų grafą, kuriame nėra ciklų. Viršūnės, atitinka miestus, o briaunos - dvikrypčius miestus jungiančius kelius. Kiekviename mieste gyvena po tam tikrą kiekį ledo ritulio fanų. Po rungtynių visi fanai pajuda iš miesto, kuriame vyko finalas, namų link. Po mačo sukeltos spūstys kelyje yra įvertinamos tuo keliu pravažiuojančių fanų skaičiui. Miesto, kuriame vyksta finalas, gyventojai, niekur keliauti neturi. Gavę valstybę modeliuojantį grafą, turite nustatyti, kuriame mieste reiktų organizuoti taurės finalą, kad didžiausia spūstis kuriame nors kelyje, būtų kuo mažesnė.

Pradiniai duomenys

Pirmoje eilutėje pateikiamas skaičius () - grafo viršūnių skaičius.

Antroje eilutėje pateikiama skaičių, paeliui sunumeruotų miestų gyventojų kiekiai (miestai numeruojami nuo iki ).

Tolesnėje eilutėje pateikiama po du skaičius - ir () reiškiančių, kad miestus su numeriais ir jungia dvikryptis kelias

Duomenys yra korektiški - pradinių duomenų grafas iš tiesų yra jungus medis.

Rezultatai

Vienintelėje rezultatų eilutėje turi būti vienintelis skaičius - kokia didžiausia spūstis susidarys kelyje, jei finalas bus organizuojamas optimaliame mieste

Pavyzdžiai

5
10 10 10 20 20
0 2
1 2
2 3
3 4

30