Deimantai

Pradinių duomenų failas:

deimantai.in  

Rezultatų failas:

deimantai.out  

Laiko apribojimas:

1 s.  

Atminties apribojimas:

16 Mb.  

Užduotis

Juvelyrika užsiimanti kompanija Gem-Toys paprašė jūsų išspręsti tokį uždavinį.

Duotas jungus nekontūrinis (t.y. neturintis ciklų) grafas. Jį sudaro briaunomis sujungtų viršūnių aibė. Kadangi grafas jungus, iš kiekvienos viršūnės einant briaunomis galima pasiekti bet kurią kitą viršūnę.

Kompanija Gem-Toys pagal tokius grafus ruošiasi gaminti juvelyrinių dirbinių modelius. Vietoje viršūnių bus įdedami deimantai, o vietoj briaunų – auksinės grandinėlės. Reikalaujama, kad dviejose gretimose viršūnėse būtų skirtingų rūšių deimantai. Kiekvienam sveikajam skaičiui p egzistuoja lygiai viena deimantų rūšis, kurios vieno deimanto kaina būtų lygi p.

Parašykite programą, kuri apskaičiuotų mažiausią bendrą modeliui pagaminti reikalingų deimantų kainą.

Pradiniai duomenys

Pirmoje pradinių duomenų failo eilutėje įrašytas vienas sveikasis skaičius N, 1 <= N < 10 000. Tai grafo viršūnių skaičius. Viršūnės sunumeruotos nuo 1 iki N. Tolesnėse N – 1 eilučių aprašomos briaunos, vienai briaunai skiriant vieną eilutę. Kiekvienoje tų eilučių yra po du tarpu atskirtus skaičius A ir B, 1 <= A,B <= N, A <> B. Tokia pora atitinka briauną, jungiančią viršūnes A ir B.

Rezultatai

Vienintelėje rezultatų failo eilutėje jūsų programa turėtų įrašyti vieną sveikąjį skaičių – juvelyrinio dirbinio modeliui pagaminti reikalingų brangakmenių bendrą mažiausią kainą.

Pavyzdžiai

8
1 2
3 1
1 4
5 6
1 5
5 7
5 8

11