Dārgakmeņu kompānija "Gem-Toys Company" lūdz jūsu palīdzību kāda uzdevuma atrisināšanā.
Ir dots sakarīgs aciklisks grafs, t.i. virsotņu kopa, ko saista šķautnes tā, ka no katras virsotnes var nokļūt uz jebkuru citu ejot tikai pa šķautnēm, un nav iespējams nokļūt vēlreiz vienā un tajā pašā virsotnē, otrreiz neejot pa vienu un to pašu šķautni.
Kompānija gatavojas no dārgakmeņiem veidot šādu grafu modeļus. Virsotnes tiks veidotas no dārgakmeņiem, bet šķautnes no zelta diega. Ir nepieciešams, lai blakus virsotnēs atrastos dažāda veida dārgakmeņi. Katram veselam pozitīvam skaitlim p ir tieši viens dārgakmeņu veids, kura cena ir p.
Uzrakstiet programmu, kas aprēķina mazāko iespējamo modelī izmantoto dārgakmeņu kopējo cenu!
Faila gems.in pirmajā rindā ir dots viens naturāls skaitlis - virsotņu skaits N(1 ≤N≤10000). Virsotnes ir numurētas ar naturāliem skaitļiem pēc kārtas no 1 līdz N. Sekojošajās N-1 faila rindās ir aprakstītas šķautnes - pa vienai katrā rindā. Katrā no šīm rindām ir divi naturāli skaitļi A un B (1 ≤A,B≤ N,A≠B), kas atdalīti ar tukšumsimbolu.Šie skaitļi apzīmē šķautni, kas savieno virsotnes A un B.
Jūsu programmai izvaddatu failā gems.out jāizvada viens naturāls skaitlis - mazākā iespējamā modelī izmantoto dārgakmeņu cena.
| gems.in | gems.out |
8 1 2 3 1 1 4 5 6 1 5 5 7 5 8 |
11 |