Nosaukums
Dārgakmeņi (gems)
Laika limits
1.00s
Atmiņas limits
256.0 MB
Grūtība
25%

Definīcija

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!


Ievaddatu raksturojums

Ievaddatu 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,AB), kas atdalīti ar tukšumsimbolu.Šie skaitļi apzīmē šķautni, kas savieno virsotnes A un B.


Izvaddatu raksturojums

Jūsu programmai izvaddatos jāizvada viens naturāls skaitlis - mazākā iespējamā modelī izmantoto dārgakmeņu cena.


Piezīmes

Uzdevums izmantots Baltijas 9.informātikas olimpiādē Tartu(Igaunija) 2003.gadā


Paraugdati

Stdin
8
1 2
3 1
1 4
5 6
1 5
5 7
5 8
Stdout
11

Uzdevums tiek aizsargāts ar autortiesībām un tā kopēšana vai neatļauta izmantošana ir aizliegta.